The recurrence T(n) = 2T(n - 2) + n describes the running time of algorithm A. A competing algorithm A' has a running time of T'(n)=16T'(n - b) + n. What is the smallest integer value for b such that A' is asymptotically faster than A?

Assume the same Case applies to both Algorithms.

T(n)=aT(nb)+f(n)a>1,b>0andf(n)=(nk)wherek0Case1:ifa1,thenO(nkabn)orO(f(n)abn) T(n)=aT(bn)+f(n)a1,b>1andf(n)=(nklogpn)Case1:iflogba>kthen(nlogba)Case2:iflogba=kifp>1,then(nklogp+1n)ifp=1,then(nkloglogn)ifp