Solve recurrence relations

Question

A) Solve this recurrence where $T(0)=0$ and write it in O-notation: $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$

So, I started to calculate:

$T(1)=2(0)+c=c$

$T(2)=1(0+c)+c=2c$

and so on, which gives me that $T(n)=nc$

This I can prove by induction: $(n-1) \rightarrow n$

$T(n)= {2 \over n} (0+c+2c+...+(n-1)c)+c = {2 \over n} (c{(n-1)n \over 2} )+c = nc$

Which gives me $O(n)$ (since $c$ is a constant). Am I right with this?

---

B) For $T(n)=kT({n \over k})+ckn$ find the closed form for the function $T(n)=f(c,k,n)$ (I don't know what does this mean) and write it in $\mathcal O$-notation. If you had the algorithm working with $k=2$, $k=3$ or $k=4$ which one would you choose?

I'm stuck with this problem. With the help of the master theorem, I would get $log_k k = 1$ which would give $\mathcal O(n \log n)$ but how to find the closed form?

Answer 1

To make life simple, assume $T(1)=1$. If we look at this just for integral powers of $k$, i.e. $n=k^m$ for some $k \in \mathbb Z$, we have, by definition, $$ T(k^m)=kT(k^{m-1})+ck\cdot k^m $$ We can repeatedly substitute into the recurrence to get: $$\begin{align} T(k^m)&=k\cdot{\color{red}{T(k^{m-1})}}+ck\cdot k^m\\ &=k\cdot{\color{red}{[k\cdot T(k^{m-2})+ck\cdot k^{m-1}]}}+ck\cdot k^m \\ &= k^2\cdot T(k^{m-2})+2ck\cdot k^m\\ &= k^3\cdot T(k^{m-3})+3ck\cdot k^m\\ &= k^4\cdot T(k^{m-4})+4ck\cdot k^m \end{align}$$ and in general we have $$ T(k^m) = k^j\cdot T(k^{m-j})+jck\cdot k^m $$ which could be formally proved by induction.

The whole point of this iterative expansion, as it's known, is to drive the $T(\cdot)$ on the right side to a value we know, namely $T(1)$, so we'll let $j=m$ to obtain $$ T(k^m) = k^m\cdot T(k^0)+mck\cdot k^m=k^m\cdot T(1)+mck\cdot k^m=k^m+mck\cdot k^m $$ Finally, since we assumed that $n=k^m$, we have $m=\log_kn$ and the expression above becomes: $$ T(n)=n+ckn\log_k n=n(1+ck\log_kn) $$

For the next part, presumably you're being asked which of $k=2, 3, 4$ will make $T(\cdot)$ smallest. For example, which is eventually smaller, $2\log_2n$ or $3\log_3n$? You should be able to answer this with a modicum of effort.

Answer 2

This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.

An easy road is to write: \begin{align} (n + 1) T(n + 1) &= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\ n T(n) &= 2 \sum_{0 \le k \le n - 1} T(k) + n c \end{align} Subtract to get: $$ (n + 1) T(n + 1) - (n + 2) T(n) = c $$ This is a linear recurrence of the first order. Divide by $(n + 1) (n + 2)$ to get: \begin{align} \frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1} &= \frac{c}{(n + 1) (n + 2)} \\ \sum_{0 \le k \le n - 1} \left( \frac{T(k + 1)}{k + 2} - \frac{T(k)}{k + 1} \right) &= c \sum_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\ \frac{T(n)}{n + 1} - T(0) &= c \sum_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\ &= c \left( 1 - \frac{1}{n + 1} \right) \\ &= c \frac{n}{n + 1} \\ T(n) &= T(0) (n + 1) + c n \end{align}