# 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:

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

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

3. $(E-1)t = \log_2(n)$

4. $(E-1)(E-1)^2t = 0$

5. $(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?

-
Clearly $T(n)=a+\log_2 n!$ by induction. But $n!\le n^n$ and $n\log n =\mathcal{O}(n^2)$ so ... am I missing something? Anyway, where does #4 come from? – anon Feb 27 '12 at 3:28
@anon 4. Comes from a nullator table. $<digit>$ gets null with $(E-1)$; $<n>$ with $(E-1)^2$; $<2n+digit>$ with $(E-1)^2$ and so on. (Excuse my mathematical informality but I'm an engineering student not a mathematician). – Randolf Rincón Fadul Feb 27 '12 at 3:36
I have no idea what any of that means. Oh well. – anon Feb 27 '12 at 3:40
If $T(n+1)=T(n)+a_n$ then $T(n+1)=a_n+a_{n-1}+\cdots+a_2+a_1+T(1)$ by applying the recurrence $n$ times. (I incorrectly said $T(n)$ instead of $T(n+1)$ in my comment above.) My assumption is that $E$ is the operator sending the function $n\to T(n)$ to $n\to T(n+1)-T(n)$, in which case it is not true that $(E-1)^3T$ is identically zero, as point 4 states. – anon Feb 27 '12 at 3:55
I don’t see a way to avoid induction completely, but in my answer I suggest a way to make it a very easy, obvious induction. (Don’t worry about the mistranslation; you included enough information to make clear what you meant.) – Brian M. Scott Feb 27 '12 at 4:05

## 2 Answers

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

-
Actually, $S(2)=1\cdot 2^a$ and so forth. You made the same mistake I did in my first comment. :) – anon Feb 27 '12 at 4:11
@anon: Sure did; thanks. Fixed now. I decided to leave the last line as is. – Brian M. Scott Feb 27 '12 at 4:31
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.

-
Aside: While $(E-1)^2 \log_2 n$ is not zero, it is pretty close. I bet there is a perfectly rigorous argument involving replacing it with an upper bound. – Hurkyl Feb 27 '12 at 4:50