1
$\begingroup$

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.

  • 0
    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.2011-08-15

2 Answers 2

2

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:
$W(k+1)=2W(k)+2^{k+1}=(2k)(2^k)+2^{k+1}k2^{k+1}+2^{k+1}=(k+1)2^{k+1}.$

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

  • 0
    @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.2011-08-15
1

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