Question 7603 – Algorithms
November 27, 2023Question 11910 – Algorithms
November 27, 2023Question 7711 – Algorithms
Give asymptotic upper and lower bound for T(n) given below. Assume T(n) is constant for n≤2.
T(n)= 4T(√n)+lg^2 n
Correct Answer: C
Question 372 Explanation:
Cosider m=log^2 n
T(2^m)=4T(2^(m/2))+m
Then S(m)=4(2^m) produces the recurrence:
S(m)=4S(m/2)+m
T(n)=T(2^m)
= S(m)=O(mlogm)
T(n)=O(lg^2 n (lg lgn))
Note: lg is nothing but log. Both are correct.
T(2^m)=4T(2^(m/2))+m
Then S(m)=4(2^m) produces the recurrence:
S(m)=4S(m/2)+m
T(n)=T(2^m)
= S(m)=O(mlogm)
T(n)=O(lg^2 n (lg lgn))
Note: lg is nothing but log. Both are correct.
T(n)= θ(lg*(lg^2 n)lg n)
T(n)= θ(lg^2n lg n)
T(n)= θ(lg^2 n (lg lg n))
T(n)= θ(lg (lg n)lg n)
Subscribe
Login
0 Comments