Is this recurrence $O(n^2)$? Is this recurrence $O(n^2)$?
$$
\begin{cases}
T(1) = a\\
T(n+1) = T(n) + \log_2(n), n\geq 1 \\
\end{cases}
$$
I try to solve it like this:


*

*$T(n+1) = T(n) + \log_2(n), n \geq 1 $

*$T(n+1) - T(n) = \log_2(n), n \geq 1 $

*$(E-1)t = \log_2(n)$

*$(E-1)(E-1)^2t = 0$

*$(E-1)^3t = 0$
So the three roots are equal to $1$ and the non-recurrent form is:
$T(n) = \alpha + \beta n + \gamma n^2 $
I can solve the coeficients in terms of $a$ but don't think it's necessary given the $\gamma n^2$ is obviously $O(n^2)$.
But I'm not sure about my solution. Why? Well because on ($4$) I use the $(E-1)^2$ annihilator which I know is proper for $n$  but not sure if its proper also for $\log_2(n)$
So is my solution correct? 
 A: Define a new function $S(n)=2^{T(n)}$. Then $S(1)=2^a$, and for $n\ge 1$ we have 
$$S(n+1) = 2^{T(n) + \log_2(n)}=nS(n)\;.$$
From this it’s clear that $S(2)=1\cdot 2^a$, $S(3)=2\cdot1\cdot2^a$, and in general $S(n)=(n-1)!2^a$. Thus, $$T(n)=\log_2S(n)=\log_2 (n-1)!2^a=a+\log_2(n-1)!\;,$$ so your question boils down to asking whether $a+\log_2(n-1)!\,$ is $O(n^2)$.
Clearly $\log_2n!\le\log_2n^n=n\log_2n$, and you should easily be able to tell whether $n\log_2n$ is $O(n^2)$.
A: But I'm not sure about my solution. Why? Well because on (4) I use the 
$(E−1)^2$ annihilator which I know is proper for n but not sure if its
proper also for $log_2(n)$

Well, you really shouldn't make completely blind guesses like that. At the very least, you should try to verify your guess. In this case it's easy: just compute
$$(E-1)^2 \log_2 n = (E-1) (\log_2 (n+1) - \log_2 n)) = (\log_2 (n+2) - 2 \log_2 (n+1) + \log_2 n) = log_2 \frac{(n+2)n}{(n+1)^2}$$
so it clearly doesn't annihilate.
But in any case, you're making the problem too hard on yourself. You aren't being asked to solve the recursion for a closed form -- you're just being asked to show it's $O(n^2)$. In other words, you're being asked if there is a $C$ such that $T(n) < C n^2$, and $T$ lends itself nicely to an inductive argument:


*

*$T(1) < C$

*Assuming that $T(n) < C x^2$, can you prove $T(n+1) < C (x+1)^2$


While you could solve the recurrence, as the other answer has shown, it's a lot more work than you actually need to do to answer the question at hand.
