Cfrgtkky

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(nlg n)$:
$T(1)=2, T(2)=6, T(n) = 2T(⌊n/2⌋) + n$, where $⌊n/2⌋$. Also, conclude
that the solution is $Theta(nlg 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(nlg 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 cnlg n$ and $T(2) le c2lg 2$, then $ c ge 6$ (note that $T(1) le c1lg 1$ does not hold). I'm not sure what to do next.

I don't understand the logic .

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=6quadtext{and}quad T(3)=2T(1)+3=7;.$$

We want to choose the constant $c$ so that $T(n)le cnlg n$ for all $nge 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)=6le ccdot2lg 2=2cquadtext{and}quad T(3)=7le ccdot3lg 3;,tag{1}$$

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

You’ve already shown that $T(m)le cmlg m$ for all $m<n$ implies that $T(n)le cnlg n$ provided that $cge 1$, and taking $cge 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 3nlg n$ for all $nge 2$.

You’re also to show that $T(n)$ is $Theta(nlg n)$, so you have to show that there are $n_0$ and $c>0$ such that $T(n)ge cnlg n$ for all $nge 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 ccdot 2lg 2=2c$, or $cle 3$. But the induction step already required $cle 1$, which is a stronger requirement, so we set $c=1$. At this point we know that $T(n)ge nlg 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 nlg 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 $nlg n=m2^m=k(n)2^{k(n)}$. Now define $$g(n)=k(n)2^{k(n)};;$$ as we just saw, this is $nlg n$ when $n$ is a power of $2$, and it’s constant on the interval $(2)$. Thus, if $2^mle n<2^{m+1}$, we have $$T(n)ge T(2^m)ge 2^mlg 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 3nlg n$ for all $nge 2$. Now let $$h(n)=frac{n}2lgfrac{n}2=frac{n}2(lg n-1)=frac{n}4lg n+frac{n}4(lg n-2)gefrac{n}4lg n$$ whenever $nge 4$. Moreover, $k(n/2)=k(n)-1$, so $h(n)<g(n)$ for all $n$, and we have finally

$$frac14nlg nle h(n)le g(n)le T(n)le 3nlg n$$ for all $nge 4$, showing that $T(n)$ is indeed $Theta(nlg n)$.

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 $nge 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_{lfloorlog_2 nrfloor-1}=0] left(2^{lfloorlog_2 nrfloor-1}b - 2^{lfloorlog_2 nrfloor+1}right)
+ [d_{lfloorlog_2 nrfloor-1}=1] left(2^{lfloorlog_2 nrfloor}a - 2^{lfloorlog_2 nrfloor}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 $Thetaleft(2^{lfloorlog_2 nrfloor}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).$$