# What is the lower bound for the following equation

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.

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

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