Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 R-F Feb 27 '12 at 3:36
    
I have no idea what any of that means. Oh well. –  anon Feb 27 '12 at 3:40
1  
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
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.) –  Brian M. Scott Feb 27 '12 at 4:05

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.