Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $T(N) = 2 T(\frac{N}{2}) + N$, where $T(1) = 0$ and $N = 2^{n}$ where $n \in N$.

I get $ \alpha ^{n-1} (\alpha -2) = \frac{n}{C}$, using the general difference equation formula.

My sketch:

3^{n-1}  T(n)   n
1        0      1
3        2      2
9        8      3
27       24     4
81       62     5

So my guess $O(T(N)) = 3^{N}$.

Now $ 3^{n-1} (3 -2) = \frac{n}{C}$ so $3^{n-1} = \frac{n}{C}$. So $(n-1) \ln(3) = \ln(n) - \ln(C)$ so

$n - \ln(n) = K$,

where $K=\ln(3) - \ln(C)$.

But I cannot see why it would be a solution.

share|cite|improve this question
Please make the body of your question self-contained. The title is not part of the message, it's an indexing feature. Books don't ask you to read the spine in order to understand the first page. – Arturo Magidin Aug 14 '11 at 22:34
Either I am missing something or the question and its title are 100% unrelated. – Did Aug 14 '11 at 23:05
Showing your calculations is good, but you never quite said what it is that you would like to show. In your table, the label should not be $T(n)$, you are listing $T(\log_2 N)$. By the way, there is a little error, $62$ should be $64$. If you make the question clear, I can give a sample solution. – André Nicolas Aug 15 '11 at 1:17
up vote 2 down vote accepted

We approach the problem in various related ways. First we set up some notation. We are working with powers of $2$. Thus it may be a good idea to let $N=2^n$. So $n=\log_2(N)$. Let $$W(n)=T(N)=T(2^n).$$

Then our recurrence can be rewritten as $$W(n)=2W(n-1)+2^n$$ with the initial condition $W(n)=0$.

First approach: Make a table very much like the table that you drew up. The indices in your table are not quite right, since $T(1)=0$, but $N=1$ corresponds to $n=0$.

Compute. We have $W(0)=0$, $W(1)=2$, $W(2)=8$, $W(3)=24$, $W(4)=64$, $W(5)=160$, $W(6)=384$.

Note that $W(0)=0\cdot 2^0$, $W(1)=2\cdot 2^1$, $W(2)=2\cdot 2^2$, $W(3)=3\cdot 2^3$, and $W(5)=5 \cdot 2^5$. It is reasonable to conjecture that $W(n)=n2^n$.

This is easy to verify by induction. The result holds at $n=0$. Suppose that it holds at $n=k$. We show that it holds at $n=k+1$.

This is straightforward:

Now let's put things back in terms of $T$ and $N$. Recall that $n=\log_2 N$. Then $$T(N)=W{2^n}=n2^n =N\log_2 N.$$ (At the end, we reversed order of typographical reasons.)

Thus we can write $T(N)=O(N\log_2 N)$. (We have proved something quite a bit stronger.)

Second approach: This is a variant of the first approach. You drew up a table. That was a very good idea. Imagine making a careful table that gives $N$, $n$, and $T(N)$. The pattern is likely to jump out.

Even better, make a simple table that gives $N$, maybe $n$, and definitely $T(N)$, and (important) $T(N)/N$. Immediately, everything becomes clear. Do it!

Unfortunately, the $n$ in your table were off by $1$, $N$ was not given, and there was a little mistake, $62$ should have been $64$. That made it difficult to see a pattern.

Third approach: In the first approach, we arrived at the linear recurrence $W(n)=2W(n-1)+2^n$. Unfortunately the recurrence is not homogeneous. Perhaps you have been taught general techniques for dealing with such recurrences. The homogeneous part $W(n)=2W(n-1)$ is easy to solve. But we also need a particular solution of the full non-homogeneous equation. You may have been taught some techniques, or that may have been dealt with by guessing, which really leaves us no better off than with the first approach.

However, there is a little trick that will make everything collapse! We make this recurrence look nicer by letting $W(n)=2^nQ(n)$. Then our recurrence can be rewritten as $$2^nQ(n)=(2)(2^{n-1}Q(n-1)+2^n,$$ which simplifies to $Q(n)=Q(n-1)+1$, with $Q(0)=0$. The solution of this recurrence is hard to miss!

Fourth approach: We were "lucky" that the recurrence had a simple explicit solution. But even if we had something a little messier, we could guess a simple function $f(N)$ such that $T(N)=O(f(N))$. Now we need to prove it. We want to show there is a constant $k$ such that $T(N) \le kf(N)$.

Then we can use the recurrence to prove that if $T(N)\le kf(N)$, then $T(2N)\le kf(2N)$. In our case, pick $f(N)=N\log N)$. The rest is not difficult. This sort of approach is important, since in general we cannot reasonably expect exact solutions. But until one acquires some experience, it may feel harder than exact solutions (in fact it is easier).

share|cite|improve this answer
I don't understand the fourth approach. Can you really find the formula with somehow testing just upper bounds? How does it work? – hhh Aug 15 '11 at 5:12
@hhh: There is no universal procedure! But let's guess that $T(N) \le 10N\log N$. Now we show that if $T(M) \le 10M\log M)$, then $T(2M)\le 10(2M)\log(2M)$, which settles the matter. The idea is that by the recurrence, $T(2M)=2T(M)+2M$. Use the inequality for $T(M)$. We get $T(2M) \le 20 M\log M +2M$. But $\log(2M)=\log 2 +\log M$, so $T(2M)\le 10(2M)\log(2M) +(2M-20M\log 2)$. Finally, $2M-20M\log 2$ is negative, and we are finished. Not much fun, but routine after the first few times. You have worked a lot more with equations than inequalities, that's why it may seem hard. – André Nicolas Aug 15 '11 at 5:56

You appear to have defined $T$ by the recurrence $T(2^n) = 2T(2^{n-1})+2^n$ for $n>0$, with initial condition $T(1)=0$. At least this more or less matches your table, except that $62$ should be $64$ (as André noted), and your $T(n)$ column is actually $T(2^{n-1})$. To see more clearly what’s going on, replace $T$ by the function $t$ defined as follows: $t(0)=0$, and $t(n)=2t(n-1)+2^n$ for $n>0$. It’s easy to check that $t(n) = T(2^n)$ for all $n \ge 0$. A closed form for $t(n)$ can be found by a variety of elementary means, but perhaps the most efficient is to let $s(n) = \frac{t(n)}{2^n}$; then $s$ satisfies the recurrence $$s(n) = \frac{t(n)}{2^n} = \frac{2t(n-1)+2^n}{2^n} = s(n-1)+1$$ for $n>0$ with initial condition $s(0) = 0$. Clearly $s(n) = n$ for all $n\ge 0$, so $T(2^n) = t(n) = n2^n$ for all $n\ge 0$.

But I cannot see what this has to do with your title or with the equation $\alpha^{n-1}(\alpha-2)=\frac{n}{C}$.

share|cite|improve this answer

Your Answer


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.