Menu
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?
513
xn + 1 = f(xn) ; n>0 We can also define a recurrence relation as an expression that represents each element of a series as a function of the preceding ones.
The recursive relation must be T(n) = T(n-1)+n for getting O(n^2) as the complexity.
Hence the complexity of above Algorithm is O(logn).
You can use generating functions, as we did in the single variable case. Let G(x,y)=∑m,n≥0F(n,m)xnym.
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).
29
answered Oct 03 '22 06:10
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.
64
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
