Solve the recurrence for n being a power of k, using the given hint

Question

$$T_n = kT_{n/k}+C\log_2{n} $$

---

C is a positive constant. I think the answer is O(n), but I don't know how to derive with the given hint and without using the master theorem. Can anyone help me please, heaps thanks! enter image description here

Answer 1

you can try to find the amount of operation (cost) in every lair in the recursive tree: in first layer its $C\log_2 n$. in second layer its k times of $C\log_2 n/k$ so its $k C\log_2 (n/k)$. in third its $k^2 C\log_2 (n/k^2)$. in the i'sh layer its $k^i C\log_2 (n/k^i)$. the depth is $\log_k n$ (cause the recursive stops when $n/k^i = 1$), so you need to calculate what is $\sum_{i=0}^{\log_k n} k^i C \log_2 (n/k^i)$