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.

  • $\begingroup$ As long as $a \neq 0$, yes. $\endgroup$ – Ian Mar 18 '16 at 16:16
  • $\begingroup$ You can say that as an answer; that will help me. $\endgroup$ – Obinna Nwakwue Mar 18 '16 at 16:19

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


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.