1

In an example presented in a lecture slide, the big-o analysis confuses me.

It states: 2n^2 + 4n = O(n^2) AND 2n^2 + 4n = O(n^4)

Can someone explain how the same equation can produce different results? Thanks

dwtrn
  • 11
  • 1
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – meowgoesthedog Oct 05 '17 at 10:05

1 Answers1

1

First of all "=" does not mean its "is equal to", it means "is" in the sense of analysis of algorithms. The point of big-O is to satisfy this:

f(x) is O(g(x)) iff 0<=|f(x)|<=c*g(x) where c is positive number.

So, in your case 2n^2 + 4n = O(n^2) AND 2n^2 + 4n = O(n^4) is true. But, we always use the "best function" here to describe the algorithm, so we use O(n^2).

From the other side, f(x) is Ω(h(x)) iff 0<=c*h(x)<=|f(x)|. Now, if you have h(x)=g(x), that means f(x) is Θ(g(x))

Adnan Isajbegovic
  • 2,227
  • 17
  • 27