0

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!

Ruben P
  • 1

2 Answers2

1

$$\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.

DanielV
  • 23,556
  • I think you solved it for a wrong version of the recurrence, i edited it because i wrote it wrong. Sorry! – Ruben P Jun 24 '15 at 18:31
  • @RubenP Can you adopt this answer to your edited case? It should be straightforward if you understand it. – DanielV Jun 24 '15 at 20:34
1

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.

marty cohen
  • 107,799
  • Indeed, in general $$\lfloor \lfloor a / b \rfloor / c \rfloor = \lfloor a / (b~c) \rfloor = \lfloor \lfloor a / c \rfloor / b \rfloor $$ . Also since he is asking for asymptotic behavior, I think that it is fair to assume that he is working with $\mathbb R$ instead of just $\mathbb N$. Same answer either way though (except that the initial case shouldn't be $T(0)$). – DanielV Jun 24 '15 at 20:34
  • Bot if you work with R, you never get to 0, so the recursion never terminates. – marty cohen Jun 25 '15 at 06:22