Recurrence relation: T(n) = T(n/2) + n

Question

Hi there I am trying to solve the following recurrence relation by telescoping but I am stuck on the last step.

T(N) = T(N/2) + N              T(1)=0
T(N/2) = T(N/4) + N/2
T(N/4) = T(N/8) + N/4
...
T(2) = T(1) + 2

T(N)= T(1) + N + N/2 + N/4

I think the answer is nlogn but I don't know how to interpret the above as nlogn. I can see that I am doing logn steps but where does the n come from?

Answer 1

The answer is not nlogn but simply n

T(1)=0

T(N) = T(N/2) + N

T(N/2) = T(N/4) + N/2

T(N/4) = T(N/8) + N/4 ... T(2) = T(1) + 2

there are totally log(N) statements in the telescopic expansion

now by telescopic cancellation,

we have T(N) = T(1) + N + N/2 + N/4 + N/8 +.....+ 2

T(1) = 0

T(N) = N + N/2 + ..... + 2

this is a Geometric series with log(n) terms and each term gets halved.

T(N) = N [ 1 - (1/2)^log(N)] / (1/2)

T(N) = 2N[1 - 1/N]

T(N) = 2N - 2

Hence answer is O(N).

Answer 2

You have done everything absolutely correctly, but was not able to find a sum. You got: n + n/2 + n/4 + ..., which is equal to n * (1 + 1/2 + 1/4 + ...).

You got a sum of geometric series, which is equal to 2. Therefore your sum is 2n. So the complexity is O(n).

P.S. this is not called telescoping. Telescoping in math is when the subsequent terms cancel each other.