2
$\begingroup$

This question already has an answer here:

I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:

$$ T(n) = \begin{cases} k\cdot T(\frac{n}{k}) & n > 0\\ 1 & n = 0\\ \end{cases} $$

where $k$ is a constant number.

I tried drawing a recurrence tree or replacing for lower $n$s but no success. I hope you can help me with an idea!

$\endgroup$

marked as duplicate by David Richerby, D.W., Juho, Rick Decker, Yuval Filmus Jun 25 '15 at 1:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Do you really mean $T(nk)$? Is $k < 1$? $\endgroup$ – Yuval Filmus Jun 24 '15 at 18:02
  • $\begingroup$ Sorry, i edited it wrong. Now is correct $\endgroup$ – Ruben P Jun 24 '15 at 18:27
2
$\begingroup$

Suppose that $n$ is a power of $k$, say $n = k^t$. Then $$ T(k^t) = kT(k^{t-1}) = k^2T(k^{t-2}) = \cdots = k^tT(1) = k^t, $$ assuming a base case of $T(1) = 1$. So for powers of $k$, we have $T(n) = n$. You can also prove that by induction: if $T(n/k) = n/k$ then $T(n) = kT(n/k) = k(n/k) = n$.

$\endgroup$

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