Question

Find an asymptotic upper bound on T(N) using the iterative method: T(n)=4T(n/2)+n2

Answer 1

Answer:

Given , T(n) = 4T(n/2 ) + n^2 -----> (A)

T(n/2) = 4T(n/4) + n^2/4

Substitute the value of T(n/2) in (A), we get

T(n) = n^2 + 4 [ 4T(n/4) + n^2/4]

= 2n^2 + 16 T(n/4)

=> T(n) = 2n^2 + 4^2 T(n/4) ----(B)

Now, T(n/4) = 2n^2 + 4 [ 16 T(n/16 + n/16]

= 3n^2 + 64 T(n/16) + n/16

=> T(n) = 3n^2 + 64T(n/16) + n/14)

.

.

.

k * n^2 + 4 ^k T(n/2^k)

This whole process will stop when 2^k reaches n

n = 2^k

=> log n = k

=> T(n) = logn * n^2 + 4^logn T(n/2^logn)

= n^2 * logn + n * T(1)

= n^2 * logn + n

Thus T(n) = n^2*logn + n

=> T(n) = O(n^2 * logn)