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.

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of.

Consider this problem:

Show that the solution of the following recurrence is $O(n\lg n)$: $T(1)=2, T(2)=6, T(n) = 2T(⌊n/2⌋) + n$, where $⌊n/2⌋$. Also, conclude that the solution is $\Theta(n\lg n)$ by proving that the solution is $O(n \lg n)$. Solve for constants and boundary conditions. Do not ignore the floor function.

It's trivial to use to substitution method to show that $T(n) = 2T(⌊n/2⌋) + n$ is $O(n\lg n)$, but I'm not sure what I'm supposed to do with the provided boundary conditions.

One thing we can state is that since $T(n) \le cn\lg n$ and $T(2) \le c2\lg 2$, then $ c \ge 6$ (note that $T(1) \le c1\lg 1$ does not hold). I'm not sure what to do next.

These slides (starting slide 10) seem to be relevant, but I don't understand the logic followed.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Your boundary condition is $T(1)=2$; the recurrence itself is identical to the one treated in the example in the PDF. Since $T(1)=2$, we must have

$$T(2)=2T(1)+2=6\quad\text{and}\quad T(3)=2T(1)+3=7\;.$$

We want to choose the constant $c$ so that $T(n)\le cn\lg n$ for all $n\ge 2$. (I.e., we’re trying to make things work with $n_0=2$, since we know that we can’t find a $c$ that works for $n=1$.) If $c$ is to work for $n=2$ and $n=3$, we must have

$$T(2)=6\le c\cdot2\lg 2=2c\quad\text{and}\quad T(3)=7\le c\cdot3\lg 3\;,\tag{1}$$

which means that we must have $c\ge 3$ and $c\ge\dfrac7{3\lg 3}$. Now $3>2\sqrt2$, so $3\lg 3>3\lg 2^{3/2}=\frac92$, and $\frac7{3\lg 3}<\frac7{9/2}=\frac{14}9<3$. That is, $$\max\left\{3,\frac7{3\lg 3}\right\}=3\;,$$ so we must have $c\ge 3$ to ensure that $(1)$ is true.

You’ve already shown that $T(m)\le cm\lg m$ for all $m<n$ implies that $T(n)\le cn\lg n$ provided that $c\ge 1$, and taking $c\ge 3$ means that $(1)$ holds to get the induction started. We’ve shown, therefore, that we can take $n_0=2$ and $c=3$: $T(n)\le 3n\lg n$ for all $n\ge 2$.

You’re also to show that $T(n)$ is $\Theta(n\lg n)$, so you have to show that there are $n_0$ and $c>0$ such that $T(n)\ge cn\lg n$ for all $n\ge n_0$. The calculations on the top half of the slide a lower bound - part $1$ of $4$ go through without change. Those at the bottom of the slide require only minor change: we have $T(2)=6$, so we need $c$ to satisfy $6=T(2)\ge c\cdot 2\lg 2=2c$, or $c\le 3$. But the induction step already required $c\le 1$, which is a stronger requirement, so we set $c=1$. At this point we know that $T(n)\ge n\lg n$ whenever $n$ is a power of $2$. The argument on the next two slides showing that $T(n)$ is strictly increasing goes through with just one small change: the base case is $T(1)=2<6=T(2)$.

At this point we know that $T(n)\ge n\lg n$ whenever $n$ is a power of $2$ and that $T(n)$ is strictly increasing. We’ll combine these facts to create a specific lower bound for $T(n)$. The next slide carries over without change, but I think that it might be helpful if I define the same $g$ in a slightly different way.

For each positive integer $n$ there is a unique non-negative integer $k(n)$ such that $$2^{k(n)}\le n<2^{k(n)+1}\;;\tag{2}$$ note that if $n=2^m$, then $k(n)=m$, and $n\lg n=m2^m=k(n)2^{k(n)}$. Now define $$g(n)=k(n)2^{k(n)}\;;$$ as we just saw, this is $n\lg n$ when $n$ is a power of $2$, and it’s constant on the interval $(2)$. Thus, if $2^m\le n<2^{m+1}$, we have $$T(n)\ge T(2^m)\ge 2^m\lg 2^m=m2^m=k(n)2^{k(n)}=g(n)\;,$$ and it follows that $T(n)\ge g(n)$ for all $n$.

Combining results, we have $g(n)\le T(n)\le 3n\lg n$ for all $n\ge 2$. Now let $$h(n)=\frac{n}2\lg\frac{n}2=\frac{n}2(\lg n-1)=\frac{n}4\lg n+\frac{n}4(\lg n-2)\ge\frac{n}4\lg n$$ whenever $n\ge 4$. Moreover, $k(n/2)=k(n)-1$, so $h(n)<g(n)$ for all $n$, and we have finally

$$\frac14n\lg n\le h(n)\le g(n)\le T(n)\le 3n\lg n$$ for all $n\ge 4$, showing that $T(n)$ is indeed $\Theta(n\lg n)$.

share|improve this answer
    
Thank you very very much, Brian. I was just about to give up and now I understand. Tremendously appreciated. –  David Chouinard Jan 28 '13 at 0:25
1  
@David: You’re very welcome; I’m glad that it helped. –  Brian M. Scott Jan 28 '13 at 0:27
add comment

This recurrence has the nice property that we can compute explicit values for $T(n)$ the same way as was done here, for example.

Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary digit representation of $n.$ Introduce the canonical representative of this class of recurrences, which is $S(n)$ where $S(0)=0$ and for $n\ge 1,$ $$S(n) = 2 S(\lfloor n/2 \rfloor) + n.$$ It is not difficult to see that $$ S(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Now return to $T(n)$ with $T(1) = a$ and $T(2) = b,$ where $a$ and $b$ are constants. It is quite straightforward to prove that $$ T(n) = S(n) + [d_{\lfloor\log_2 n\rfloor-1}=0] \left(2^{\lfloor\log_2 n\rfloor-1}b - 2^{\lfloor\log_2 n\rfloor+1}\right) + [d_{\lfloor\log_2 n\rfloor-1}=1] \left(2^{\lfloor\log_2 n\rfloor}a - 2^{\lfloor\log_2 n\rfloor}\right).$$

This formula is exact, no approximation involved. There is a complete detailed proof that $S(n) \in \Theta(n \log_2 n)$ posted in this message. The additional term is $\Theta\left(2^{\lfloor\log_2 n\rfloor}\right) = \Theta(n)$ in both cases, which is of lower order than the main term, so that $$T(n) \in \Theta(n \log_2 n).$$

share|improve this answer
add comment

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.