TestBook Test Series: Algorithms - Time Complexity

Question

how to solve these two using matser thorem.

1.  t(n)=2t(√n)+n

2. t(n)=4t(√n)+(logn)^2

Comments

Master's method extension

Answer 1

Substitute n as some function of 2^k. So, k = log n. Now equation will in form of 2^k. Now reduce the equation into S(k) = 2S(k/2) + k and solve using master's theorem. And replace 'k' by log n.

Comments

plz elobrate ur soln  speciallly for 2nd