1
$\begingroup$

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).

Zulfi.

$\endgroup$
3
  • 1
    $\begingroup$ Does this answer your question? Sorting functions by asymptotic growth $\endgroup$ Jan 29, 2020 at 12:23
  • $\begingroup$ Sorry I can't understand that stuff. It has very little discussion about lower bounds i.e. Omega notations. $\endgroup$ Jan 29, 2020 at 15:15
  • $\begingroup$ Being a quadratic function, it is both lower and upper bounded by n^2. $\endgroup$ Jan 29, 2020 at 21:52

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
4
  • $\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, 2020 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, 2020 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, 2020 at 4:48
  • 1
    $\begingroup$ f(n)=n, g(n)=n^2, n in O(f(n)) and O(g(n)) $\endgroup$ Jan 30, 2020 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.