2
$\begingroup$

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?

  • 1
    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.)2012-02-27

2 Answers 2

4

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

  • 0
    @anon: Sure did; thanks. Fixed now. I decided to leave the last line as is.2012-02-27
0
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.

  • 0
    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.2012-02-27