Recurrences

Problem 1

a. $T(n) = T(n - 1) + 1$

Unrolling the recurrence yields: $T(n) = 1 + T(n - 2) = 1 + 2 + T(n - 3)$
And so $T(n) = 1 + 1 + \dots + T(n - n) = \sum^n_{i=1} 1 = n$.
Thus $T(n) \in \Theta(n)$

b. $T(n) = T(n - 1) + n$

First unroll the recurrence to get $T(n) = n + T((n - 1) = n + (n-1) + T(n-2)$ and so on...
$T(n) = \sum^n_{x=3} x + \Theta(1) = \sum^n_{x=1} x - 2 - 1$
$T(n) = \frac{n(n+1)}{2} + \Theta(1)$

Thus $T(n) = \Theta(n^2)$

c. $T(n) = T(an) + T((1-a)n) + cn$

Expanding by one yields:
Level 1: $cn$
Level 2: $T(an) + T((1 - a)n)$

Expanding another time yields:
Level 1: $cn$
Level 2: $c(an) + c(1-a)n$
Level 3: $ca^2 n + ca(1 - a)n + ca(1 - a)n + c(1-a)^2 n$

And so on. Since we can assume the arguments to $T(n)$ are positive, $0 < alpha < 1$, and so we roughly split each node in half, which means that the height of the tree is $h = \Theta(\lg n)$.
Notice that on level 2 of the second expansion, we can combine terms to get: $can + cn - can = cn$. Likewise, on the third level: $ca^2 n + can - ca^2 n + can - ca^2 n + c(1-a)^2 n = 2can - ca^2 + c(1 - 2a + a^2)n = cn$.

Hence, each level adds $cn$ to $T(n)$, and so the recurrence solves to $T(n) = hcn = \Theta(n \lg n)$.

d. Solve $T(n) = 2T(n/2) + n$ using the substitution method.

You can probably assume $T(n) = O(n \lg n)$, since it has the form of a regular divide-and-conquer recurrence. So first, we show that $T(n) \leq cn\lg n$ for some $c > 0$. Plugging it in:

$T(n) \leq 2T(n/2) + n$
$T(n) \leq 2((cn/2) \lg(n/2)) + n$
$T(n) \leq cn\lg(n/2) + n$
$T(n) \leq cn\lg n - cn\lg 2 + n$
$T(n) \leq cn\lg n - cn + n$

Since $cn\lg n$ is the dominating term, we have $T(n) \leq cn\lg n$, as long as $c \geq 1$.

Problem 2

The Master method is a general method for recurrences with constants $a \geq 1$ and $b > 1$ of the following form:
$$T(n) = aT(n/b) + f(n)$$

  1. If $f(n) = O(n^{\log_b a - \epsilon})$, for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
  2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
  3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and $af(n/b) \leq cf(n)$, for some $c < 1$ and for all $n$ greater than some value $n’$, then $T(n) = \Theta(f(n))$.

Use the Master method to solve the following recurrences.

a. $T(n) = 4T(n/2) + n$

Here, $a = 4$, $b=2$, and $f(n) = n$. Considering that $\log_b a = \log_2 4 = 2$ its clear that $f(n) \in O(n^{\log_b a - \epsilon})$ for some $\epsilon$ (i.e. $\epsilon = 1/2$), so we invoke case 1 of the Master method. Thus, $T(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$

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

As before, $a = 4$, $b=2$, and $f(n) = n^3$. Since $3 > \log_b a$, case 3 seems to fit the bill. Now, consider choosing $\epsilon$ such that $0 < \epsilon < 1$. Clearly then, $n^3 = \Omega(n^{2 + \epsilon})$ which confirms that this is solved by case 3. Thus, $T(n) = \Theta(f(n)) = \Theta(n^3)$.

c. $T(n) = 4T(n/2) + n^2$

We have the same constants as before, and $f(n) = n^2$. Since $\log_b a = 2$ this is a typical case 2 problem: $n^2 = \Theta(n^2)$. And so, $T(n) = \Theta(n^2 \log n)$.

d. $T(n) = 2T(n/4) + n\lg n$

$a = 2$, $b = 4$, $f(n) = n\log n$. $\log_b a = log_4 2 = 0.5$. The third case should hold, as $n \log n = \Omega(n^{0.5 - \epsilon})$ for $\epsilon > 0$.

First though, we must verify the regularity condition and prove $2(n/4)\log(n/4) \leq cn\log(n)$ for $c < 1$. A little algebra and $(n/2)(\log n - \log 4) \leq cn\log n$ can be satisfied for $c \leq 0.5$. Hence, $T(n) = \Theta(f(n)) = \Theta(n \log n)$

Problem 3

A grab-bag of tricky problems.

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

Let $k = \lg n$ which gives us $T(2^k) = T(2^{k/2}) + 1$
We can use another recurrence, say $S(k) = T(2^k) = S(k/2) + 1 $
Using a tree we can show $S(k) = \Theta(\lg k) = T(2^k)$.

If $T(2^k) = \Theta(\lg k)$ then undoing the substitution gives us $T(n) = \Theta(\lg \lg n)$.

b. $T(n) = 2T(n/2) + n/\lg n$

If you wanted to use the Master method here, you cannot. This is because the regularity condition in case 3 does not hold, since $af(n/b) \neq cf(n)$. As you can see: $2 (n/2)/\lg n \not\leq cn/\lg n$ for $c < 1$.

Using a recursion tree, you can check that the sum of the tree at level $i$ is $\frac{n}{\log n - i}$, and the height is $h = O(\log n - 1)$. Hence the solution is $T(n) = \sum^{\log n - 1}_{i=0} \frac{n}{\log n - i}$ which solves to $\Theta(n \log \log n)$.