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.

a. $T(n) = 4T(n / 3) + n\lg n$.

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

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

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

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

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

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

h. $T(n) = T(n - 1) + \lg n$.

i. $T(n) = T(n - 2) + 1 / \lg n$.

j. $T(n) = \sqrt nT(\sqrt n) + n$

a. By master theorem, $T(n) = \Theta(n^{\log_3 4})$.

b.

By the recursion-tree method, we can guess that $T(n) = \Theta(n\log_3\log_3 n)$.

We start by proving the upper bound.

Suppose $k < n \implies T(k) \le ck \log_3\log_3 k - k$, where we subtract a lower order term to strengthen our induction hypothesis.

It follows that

$$ \begin{aligned} T(n) & \le 3 (c \frac{n}{3} \log_3\log_3 \frac{n}{3} - \frac{n}{3}) + \frac{n}{\lg n} \\ & \le c n \log_3\log_3 n - n + \frac{n}{\lg n} \\ & \le c n \log_3\log_3 n, \end{aligned} $$

if $n$ is sufficiently large.

The lower bound can proved analogously.

c. By master theorem, $T(n) = \Theta(n^{2.5})$.

d. It is $\Theta(n\lg n)$. The subtraction occurring inside the argument to $T$ won't change the asymptotics of the solution, that is, for large $n$ the division is so much more of a change than the subtraction that it is the only part that matters. once we drop that subtraction, the solution comes by the master theorem.

e. By the same reasoning as part (b), the function is $O(n\lg n)$ and $\Omega(n^{1 - \epsilon})$ for every $\epsilon$ and so is $\tilde O(n)$, see Problem 3-5.

f. We guess $T(n) \le cn$,

$$ \begin{aligned} T(n) & = T(n / 2) + T(n / 4) + T(n / 8) + n \\ & \le \frac{7}{8}cn + n \le cn. \\ \end{aligned} $$

where the last step holds for $c \ge 8$.

g. Recall that $\chi_A$ denotes the indicator function of $A$. We see that the sum is

$$T(0) + \sum_{j = 1}^n \frac{1}{j} = T(0) + \int_1^{n + 1}\sum_{j = 1}^{n + 1} \frac{\chi_{j, j + 1}(x)}{j}dx.$$

Since $\frac{1}{x}$ is monatonically decreasing, we have that for every $i \in \mathbb Z^+$,

$$\text{sup}_{x \in (i, i + 1)} \sum_{j = 1}^{n + 1} \frac{\chi_{j, j + 1}(x)}{j} - \frac{1}{x} = \frac{1}{i} - \frac{1}{i + 1} = \frac{1}{i(i + 1)}.$$

Our expression for $T(n)$ becomes

$$T(N) = T(0) + \int_1^{n + 1} \Big(\frac{1}{x} + O(\frac{1}{\lfloor x \rfloor(\lfloor x \rfloor + 1)})\Big)dx.$$

We deal with the error term by first chopping out the constant amount between 1 and 2 and then bound the error term by $O(\frac{1}{x(x - 1)})$ which has an anti-derivative (by method of partial fractions) that is $O(\frac{1}{n})$,

$$ \begin{aligned} T(N) & = \int_1^{n + 1} \frac{dx}{x} + O(\frac{1}{n}) \\ & = \lg n + T(0) + \frac{1}{2} + O(\frac{1}{n}). \end{aligned} $$

This gets us our final answer of $T(n) = \Theta(\lg n)$.

h. We see that we explicity have

$$ \begin{aligned} T(n) & = T(0) + \sum_{j = 1}^n \lg j \\ & = T(0) + \int_1^{n + 1} \sum_{j = 1}^{n + 1} \chi_{(j, j + 1)}(x) \lg j dx. \end{aligned} $$

Similarly to above, we will relate this sum to the integral of $\lg x$.

$$\text{sup}_{x \in (i, i + 1)} \sum_{j = 1}^{n + 1} \chi_{(j, j + 1)}(x) \lg j - \lg x = \lg(j + 1) - \lg j = \lg \Big(\frac{j + 1}{j}\Big).$$

Therefore,

$$ \begin{aligned} T(n) & \le \int_i^n \lg(x + 2) + \lg x - \lg(x + 1)dx \\ & (1 + O(\frac{1}{\lg n})) \Theta(n\lg n). \end{aligned} $$

i. See the approach used in the previous two parts, we will get $T(n) = \Theta(\frac{n}{\lg n})$.

j. Let $i$ be the smallest $i$ so that $n^{\frac{1}{2^i}} < 2$. We recall from a previous problem (3-6.e) that this is $\lg\lg n$ Expanding the recurrence, we have that it is

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