Does any quadratic function in the form $an^2 + bn + c$ equal $\Theta(n^2)$ in asymptotic notation?

1.1k Views Asked by At

On a Khan Academy post (see here) about Big-$\Theta$ notation, the author attempted to convert the quadratic function $6n^2 + 100n + 300$ to asymptotic notation. They started by dropping the $n^2$ coefficient in $6n^2$. They also removed the 'low-order terms' $100n + 300$ and got $\Theta(n^2)$. Apparently, this works for any function in the form $an^2 + bn + c$ because you have to remove $a$ and drop $bn + c$ to get $\Theta(n^2)$. It looks like any function in said form will have a asymptotically tight bound of $\Theta(n^2)$. Is it true that any function $f(n) = an^2 + bn + c$ will have a tight bound of $\Theta(n^2)$?

Reminders about Question

  • I do not have any problems here. I am just wondering if something is true/false.

  • I tried looking at other sources related to Big-$\Theta$, but they didn't help.

1

There are 1 best solutions below

0
On BEST ANSWER

As long as $a \neq 0$, yes. When $a=0$, you have $bn+c$, which is asymptotically smaller than $n^2$, i.e. $bn+c=o(n^2)$.