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

recurrence
Harry Tiron picture Harry Tiron · Jun 4, 2012 · Viewed 24.9k times · Source

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

Salvador Dali picture Salvador Dali · Dec 14, 2015

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.

Related questions

n log n is O(n)?

I am trying to solve this recurrence T(n) = 3 T(n/2) + n lg n .. I have come to the solution that it belongs to masters theorem case 2 since n lg n is O(n^2) but after referring to the solution …

Read More
What's the best way to model recurring events in a calendar application?

I'm building a group calendar application that needs to support recurring events, but all the solutions I've come up with to handle these events seem like a hack. I can limit how far ahead one can look, and then generate …

Read More
Solving T(n) = 4T(n/2)+n²

I am trying to solve a recurrence using substitution method. The recurrence relation is: T(n) = 4T(n/2)+n2 My guess is T(n) is Θ(nlogn) (and i am sure about it because of master theorem), and to find an …

Read More