Give asymptotic upper and lower bound for T(n) given below. Assume T(n) is constant for \(n \le 2.\;T\left( n \right) = 4T\left( {\sqrt n } \right) + lo{g^2}n\)

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) Dec 2019 Paper

Attempt Online

Answer 1

\(T\left( n \right) = 4T\left( {√ n } \right) + lo{g^2}n\)

Consider n = 2^m

m = log₂n

n = 2m

Taking square root

√n = 2m/2

T(2^m) = 4T(2^m/2) + m²

Put S(m) = T (2^m/2)

S(m) = 4 S(m/2) + m²

Comparing with

T(m) = a T(m/k) + cmk

a = 4, b = 2, k = 2

a = b^k = 4

Now use master’s theorem :

T(m) = O(mklog m)

So, Time complexity will be O(m²log m)

Put the value of m

Time complexity will be : O (log²n log (logn))