Question

3. 0 marks Suppose you have an algorithm which has the following recurrence relation for W(n), assuming n is a power of 2, i.e. assuming n-2, k20: for n for n- W()-2W(n/2)+2n+ 2 W(n)- Using back substitution and assuming n is a power of 2, ie. n-2, find an exact (ie non-recursive) formula for Win). Be sure to show your work and to simplify your final answer as much as possible. Note that you do NOT need to verify your final answer using induction

Answer 1

W(n) = 2W(n/2) + 2n + 2 for n>1

W(n) = 1 for n=1 (Base Case)

Back substitution:

W(n) = 2W(n/2) + 2n + 2

or,

W(n) = 2*[2W(n/2²) + 2n/2 + 2] + 2n + 2

or,

W(n) = 2²W(n/2²) + 2n + 2²+ 2n + 2

or,

W(n) = 2²W(n/2²) + 2*(2n) + 2² + 2

or,

W(n) = 2²[2W(n/2³) +n/2+ 2] + 2*(2n) + 2² + 2

or,

W(n) = 2³W(n/2³) +2n+ 2³+ 2*(2n) + 2² + 2

or,

W(n) = 2³W(n/2³) + 3*(2n)+ 2³ + 2² + 2

or,

W(n) = 2^kW(n/2^k) + k*(2n)+ 2^k + 2^k-1+ ...................+ 2³ + 2² + 2

Let n/2^k = 1

Therefore n = 2^k

or,

k = logn (base 2)

Now substituting k in the equation we get:-

W(n) = n*W(1) + logn*(2n)+ 2^logn + 2^logn-1+ ...................+ 2³ + 2² + 2

From the base case W(1)=1

Substituting W(1) in the equation we get:-

W(n) = n + 2nlogn+ 2^logn + 2^logn-1+ ...................+ 2³ + 2² + 2

Now 2+2²+2³+.............+2^logn is a geometric series with number of terms x=logn, first term as a=2 and common divisor as r=2.

Sum of geometric series is given by a*(r^x - 1)/(r-1)

or, 2*(2^logn - 1)/(2-1)

or, 2*(n-1)

Substituting this sum in the previous equation we get W(n) as :-

W(n) = n + 2nlogn + 2n - 2

or,

W(n) = 2nlogn + 3n - 2