I have been trying to solve this recurrence for almost 2 hours but could not get the answer...
Let:
T(n)= kn+T(n/2) for n>1 and T(1)=1 where n = 2^k for some integer k
Show that T(n)= O(n)
(I'm assuming the k in T(n) = kn + T(n / 2) is not the same as the k in n = 2^k. If that's wrong, I'll update this.)
If you just need an asymptotic bound, then you can use the Master Theorem. Your recurrence is
T(n) = T(n / 2) + kn
So a = 1, b = 2, and c = 1. Therefore, since logb a = 0 < 1, the Master Theorem causes this to solve to Θ(n).
If you need an exact value, you can use the iteration method to get a good guess. I'm assuming T(1) = 1.
T(n) = T(n / 2) + kn
= (T(n / 4) + kn/2) + kn
= T(n / 4) + kn + kn/2
= (T(n / 8) + kn / 4) + kn + kn / 2
= T(n / 8) + kn + kn / 2 + kn / 4
...
= T(n / 2i) + kn(1 + 1/2 + 1/4 + ... + 1/2i)
This terminates when i = log2 n, at which point we get
T(n) = T(1) + kn(1 + 1/2 + 1/4 + ... + 1/n)
= 1 + kn(1 + 1/2 + 1/4 + ... + 1/n)
= 2kn
So the exact figure should be (modulo math errors) 2kn, agreeing with the result from the Master Theorem.
Hope this helps!