[Solved]: Solve recurrence relations

Problem Detail: 

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?

Asked By : Wanderer

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27705

 Ask a Question

 Download Related Notes/Documents