This question already has an answer here:

How can I find the Big Theta of $(\log n)^2-9\log n+7$?

I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.


marked as duplicate by Raphael Sep 20 '18 at 21:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Your thought is in the right direction. You can eliminate the "+7" on the right and pick $c_1=1$. Then for all $n$ for which $-9\log(n)+7\le 0$ you'll have what you need to show that your function is $O(\log^2(n))$. Finding a big-Omega bound is only slightly more difficult (you can use, for example, $c=1/2$). $\endgroup$ – Rick Decker Feb 13 '16 at 18:58
  • $\begingroup$ "The Big Theta" of $(\log n)^2-9\log n+7$ if $\Theta((\log n)^2-9\log n+7)$. You'll have to phrase your question more precisely. $\endgroup$ – Raphael Sep 20 '18 at 21:29

There is no such thing as "the" big $\Theta$ of a function. For a given function $f(n)$, many functions $g(n)$ satisfy $f(n) = \Theta(g(n))$. For example, every function satisfied $f(n) = \Theta(f(n))$.

However, usually we are interested in a "succinct", "canonical" or "simple" expression $g(n)$, for example of the form $c^n n^a (\log n)^b$, for some $c \geq 1$. In your case $g(n) = (\log n)^2$: your function is $\Theta((\log n)^2)$, which is not too hard to show.

Setting the proof apart, how do I know that your function is $\Theta((\log n)^2)$? Since $(\log n)^2$ is the dominant term: all other terms ($\log n$ and $1$) grow slower than $(\log n)^2$. The constants in front of them don't matter asymptotically.

  • $\begingroup$ Why not $O(logn)^2$? $\endgroup$ – vivek Mar 7 '16 at 8:07
  • $\begingroup$ The OP asked for big Theta, not big O. $\endgroup$ – Yuval Filmus Mar 7 '16 at 8:12
  • $\begingroup$ True, but what if I say that its $O(logn)^2$? is it a valid statement? $\endgroup$ – vivek Mar 7 '16 at 8:15
  • $\begingroup$ It's much better to write it as $O(\log^2 n)$, with the square inside the big O. $\endgroup$ – Yuval Filmus Mar 7 '16 at 8:19
  • $\begingroup$ I am a beginner and finding much confusion, the problem is that I can't find a good reference. There seems a lot of confusions too in lot of text books. I recently saw this answer, can you please point me to some good reference? $\endgroup$ – vivek Mar 7 '16 at 8:23

Hint: what is the answer for $n^2-9n+7$ ?

  • 1
    $\begingroup$ Maybe The answer is Θ(n^2)??... so what's your point.... I don't want the answer like Θ(( log(n)^2) ) I need to know the way to find it... like big-O big-Ω and then theta. I can't comment(need 50 rep), that's why I made an answer.... $\endgroup$ – user46286 Feb 13 '16 at 15:56

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