# What is the Big Theta of $(\log n)^2-9\log n+7$? [duplicate]

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.

• 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$). – Rick Decker Feb 13 '16 at 18:58
• "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. – Raphael Sep 20 '18 at 21:29

## 2 Answers

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.

• Why not $O(logn)^2$? – vivek Mar 7 '16 at 8:07
• The OP asked for big Theta, not big O. – Yuval Filmus Mar 7 '16 at 8:12
• True, but what if I say that its $O(logn)^2$? is it a valid statement? – vivek Mar 7 '16 at 8:15
• It's much better to write it as $O(\log^2 n)$, with the square inside the big O. – Yuval Filmus Mar 7 '16 at 8:19
• 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? – vivek Mar 7 '16 at 8:23

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

• 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.... – user46286 Feb 13 '16 at 15:56