Solving recurrences with boundary conditions

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

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