#time complexity

Question

T(n)=4T(n/2)+n$^{2}\sqrt{2}$  T.C

Comments

$f(n)$ are given in asymptotic notation, so you can drop that constant.

---

Substitution is also easy. After $k$ iterations, the recurrence will be $T(n) = 4^kT(n/2^k) + \sqrt 2 k n^2$, where $k  =  \log n$, making it $O(n^2 \log n)$.

---

T(n)=mT(n/2)+an$^{2}$  what time complexity

Answer 1

Comparing with masters theorem
T(n)=aT(n/b)+f(n)

a=4 , b=2 n^(log a base b) is n^2
f(n) = n^2 * root(2) which is asymptotically equal to n^2 so by case 3 of masters theorem

Theta(n log a base b *(log n)^ k+1)

K is the power in f(n) ... in ques it is 0