f(n) = 32n^2 + 17n + 1.

The lecture slide says that lower bound can be Omega(n^2) or Omega(n).

Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2).



This is a quadratic function; therefore $f$ is big-Theta of $n^2$. Therefore, it is both Big-O and Big-Omega of $n^2$.

However, when a function $f$ is big-Omega of another function $g$, then $f$'s growth is of greater or equal order than $g$. However, since a quadratic grows strictly faster than a linear in the long run, $n^2$ is big-Omega of $n$. Think of as if big-Omega means "greater or equal than".

Also note when $f$ is big-Omega of $g$, then $g$ is big-O of $f$. Obviously, $n$ is big-O of both $n$ and $n^2$.

  • $\begingroup$ "Obviously, n is big-O of both n and n2. " . This does not seem correct. Big-O notation is used for functions not for variables. $\endgroup$ Jan 30 '20 at 3:04
  • $\begingroup$ Often when referring to a function f(n) where n isnt declared we simply write f as the function. Namely f=f(n) $\endgroup$ Jan 30 '20 at 3:25
  • $\begingroup$ You are not saying 'f', you are saying 'n' is big-O of both 'n' and 'n^2'. I think its a typo. Please correct it, your last line. $\endgroup$ Jan 30 '20 at 4:48
  • 1
    $\begingroup$ f(n)=n, g(n)=n^2, n in O(f(n)) and O(g(n)) $\endgroup$ Jan 30 '20 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.