4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If looks like $T(k^{m-1}) = mck^m$... $\endgroup$ – Karolis Juodelė Jun 14 '14 at 14:16
  • $\begingroup$ I don't understand this I'm afraid. Can you walk me through it? $\endgroup$ – Wanderer Jun 14 '14 at 14:44
  • $\begingroup$ $T(0) = kT(0) = 0$; $T(k^0) = kT(0)+ck = ck$; $T(k^1) = kT(1)+ck^2 = 2ck^2$ ... Of course, this isn't a complete solution. $\endgroup$ – Karolis Juodelė Jun 14 '14 at 14:44
  • $\begingroup$ You have two unrelated questions in your question. Please, stick to one question per question. For a., your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – D.W. Jun 14 '14 at 17:43
  • $\begingroup$ possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – D.W. Jun 14 '14 at 17:44
4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.