I need help in solving this recurrence [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions about general computing hardware and software on Stack Overflow. You can edit the question so it’s on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

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)

Answer 1

(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 log_b 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 / 2ⁱ) + kn(1 + 1/2 + 1/4 + ... + 1/2ⁱ)

This terminates when i = log₂ 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!