I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:
$T(n)=k * T(n / k)$
$T(0)=1$,
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!
On
I assume that only integer parameters are used, so the correct recurrence is $T(n)=k * T(\lfloor n / k \rfloor) $.
Correcting DanielV's answer, since $\lfloor \lfloor n/k \rfloor /k \rfloor =\lfloor n/k^2 \rfloor $, by induction $T(n)=k^m * T(\lfloor n / k^m \rfloor) $ for $k^m \le n $. If $m$ is the smallest value such that $k^m > n$ (this is $m > \log(n)/\log(k)$ or $m = \lceil \log(n+1)/\log(k) \rceil$ ), then, since $T(0) = 1$, $T(n) =k^m $.
Since $\log(n+1)/\log(k) \le m <1+\log(n+1)/\log(k) $, $n+1 \le k^m < k(n+1) $.
Therefore $n+1 \le T(n) < k(n+1) $, so $T(n) =\Theta(n) $.
Notice that, for the upper bound of $T(n) = O(n) $, the constant hidden by the $O(n)$ depends on $k$. Since this does not depend on $n$, this is OK.
$$\begin{align} T(n) &= k~T(k~n) \\ &= k^2~T(k^2~n) \\ &= k^3~T(k^3~n) \\ & \vdots \\ &= k^z~T(k^z~n) \\ \end{align}$$
So which $z$ to choose? Let's make the base case be $T(1) = c$, so
$$k^z~n = 1$$ $$\log(k^z~n) = \log(1)$$ $$z~\log(k) + \log(n) = 0$$ $$z = -\frac{\log(n)}{\log(k)}$$ $$z = \log_k(n^{-1})$$
So we have
$$\begin{align} T(n) &= k^{\log_k(n^{-1})} T(k^{\log_k(n^{-1})} ~ n) \\ &= n^{-1} T(1) \\ &= \frac{c}{n} \end{align}$$
So as you can see, $T(n) = k~T(k~n)$ doesn't actually depend on $k$ at all. Any $T$ that has this property for one $k$ will have it for any other $k$ (for $0 < k < 1$ anyway).
Unfortunately, since $T(n)$ is monotonically decreasing (as opposed to asymptotically increasing), this isn't a good problem to learn complexity with.