Problem 4.3

More recurrence examples

Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.

  1. $T(n) = 4T(n/3) + n\lg{n}$
  2. $T(n) = 3T(n/3) + n/\lg{n}$
  3. $T(n) = 4T(n/2) + n^2\sqrt{n}$
  4. $T(n) = 3T(n/3 - 2) + n/2$
  5. $T(n) = 2T(n/2) + n/\lg{n}$
  6. $T(n) = T(n/2) + T(n/4) + T(n/8) + n$
  7. $T(n) = T(n - 1) + 1/n$
  8. $T(n) = T(n - 1) + \lg{n}$
  9. $T(n) = T(n - 2) + 1/\lg{n}$
  10. $T(n) = \sqrt{n}T(\sqrt{n}) + n$

1. $T(n) = 4T(n/3) + n\lg{n}$

$\Theta(n^{\log_3{4}})$ by the master method.

2. $T(n) = 3T(n/3) + n/\lg{n}$

It's $\Theta(n\lg\lg{n})$. Check subtask 5 for the reasoning.

3. $T(n) = 4T(n/2) + n^2\sqrt{n}$

$\Theta(n^2\sqrt{n}) = \Theta(n^{2.5})$ by the master method ($\log_2{4} = 2 < 2.5$).

4. $T(n) = 3T(n/3 - 2) + n/2$

We can ignore the $-2$ and using the master method, we arrive at $\Theta(n\lg{n})$.

5. $T(n) = 2T(n/2) + n/\lg{n}$

$$ \begin{aligned} T(n) & = 2T(n/2) + \frac{n}{\lg{n}} = 4(n/4) + 2\frac{n/2}{\lg(n/2)} + \frac{n}{\lg{n}} = 4T(n/4) + \frac{n}{\lg{n} - 1} + \frac{n}{\lg{n}} \\ & = nT(1) + \sum_{i=0}^{\lg{n} - 1}\frac{n}{\lg{n}-i} = nT(1) + n\sum_{i=1}^{\lg{n}}\frac{1}{\lg{n}} \\ & = \Theta(n\lg\lg{n}) \end{aligned} $$

6. $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

We guess $\Theta(n)$:

$$ \begin{aligned} T(n) & = cn/2 + cn/4 + cn/8 + n \le (7/8)cn + n \le cn = O(n) \quad (c \ge 8) \\ T(n) & = cn/2 + cn/4 + cn/8 + n \ge (7/8)cn + n \ge cn = \Omega(n) \quad (c \le 8) \end{aligned} $$

7. $T(n) = T(n - 1) + 1/n$

$$ \begin{aligned} T(n) &= T(n-1) + 1/n = \frac{1}{n} + \frac{1}{n-1} + T(n-2) \\ &= \frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2} + T(n-3) \\ &= \sum_{i=0}^{n-1}\frac{1}{n-i} = \sum_{i=1}^n\frac{1}{i} = \\ &= \Theta(\lg{n}) \end{aligned} $$

8. $T(n) = T(n - 1) + \lg{n}$

$$ \begin{aligned} T(n) &= \lg{n} + T(n-1) = \lg{n} + \lg{n-1} + T(n-2) = \\ &= \sum_{i=0}^{n-1}\lg(n - i) = \sum_{i=1}^{n}\lg{i} = \lg(n!) \le \lg{n^n} = n\lg{n} \\ &= \Theta(n\lg{n}) \end{aligned} $$

9. $T(n) = T(n - 2) + 1/\lg{n}$

$$ \begin{aligned} T(n) &= \frac{1}{\lg{n}} + \frac{1}{\lg{n-2}} + \ldots \\ &= \sum_{i=1}^{n/2}\frac{1}{\lg(2i)} \\ &= \sum_{i=1}^{\infty}\frac{1}{\lg{i}} \\ &= \Theta(\lg\lg{n}) \end{aligned} $$

10. $T(n) = \sqrt{n}T(\sqrt{n}) + n$

Let $n = 2^m$, or $m = \lg{n}$. We use this to get another recurrence in hopes of being able to use the master theorem on it:

$$ \begin{aligned} T(2^m) &= \sqrt{2^m}T(\sqrt{2^m}) + 2^m \\ &= 2^{m/2}T(2^{m/2}) + 2^m \\ Q(m) &= 2^{m/2} Q(m/2) + 2^m \end{aligned} $$

We still cannot use the master theorem. Now multiply $Q(m)$ by $\frac{1}{2^m}$ to get: $R(m) = R(m/2) + 1$. Now we can use the master theorem to compare $f(n) = 1$ and $n^{log_b a} = n^{log_2 1} = n^0 = 1$. Since $n^{log_b a} = f(n)$:

$$ \begin{aligned} R(m) &= \Theta(1 \times \lg{m}) \\ Q(m) &= \Theta(2^m \lg{m}) \\ T(m) &= \Theta(2^{\lg{n}} \lg{\lg{n}}) \\ & = \Theta(n \lg{\lg{n}}) \end{aligned}$$

We verify $T(n) \le cn\lg\lg{n}$:

$$ \begin{aligned} T(n) &\le \sqrt{n}c\sqrt{n}\lg\lg\sqrt{n} + n \\ & = cn\lg\lg\sqrt{n} + n \\ & = cn\lg\frac{\lg{n}}{2} + n \\ & = cn\lg\lg{n} - cn\lg{2} + n \\ & = cn\lg\lg{n} + (1 - c)n & (c > 1) \\ &\le cn\lg\lg{n} & = \Theta(n\lg\lg{n}) \end{aligned} $$