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?