Algo: Time complexity

Question

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

In thetha notation?

Comments

According to Master's Theorem, it should be $\Theta(n^{2} logn)$
Is it ?

---

In made easy test series they have given thetha(n^2.5). But i got the same as your as logn is less than squareroot(n)

---

The last term can be rewritten as $n^{2}\sqrt{2} = n^{2} * 2^{1/2} = n^{2} \log_{2} 2^{2^{1/2}}$

According to Masters Theorem, a >= 1, b > 1, p = 1 in the equation

$T(n) = aT(n/b) + \Theta(n^{k} log^{p} n)$

SInce p > -1, So

$T(n) = \Theta(n^{\log_{b}a} \log^{p+1}n) = \Theta(n^{2} \log^{2}n) = \Theta(n^{2} \log\log n)$

Not sure if this is right

---

@ rishi71662data4 

$T(n) = aT(n/b) + \Theta(n^{k} log^{p} n)$ this is correct. But here $f(n)$ is not in that form. Answer is $\Theta(n^{2} logn)$

---

^^Okay, I think my forceful assumption about the value of p with logn was a stupid mistake.

Answer 1

$T\left ( n \right )=4 \times T\left ( \frac{n}{2} \right )+n^{2}\,\sqrt{2}$

$T\left ( \frac{n}{2} \right )=4 \times T\left ( \frac{n}{4} \right )+\left ( \frac{n}{2} \right )^{2}\,\sqrt{2}................(1)$

$T\left ( \frac{n}{4} \right )=4 \times T\left ( \frac{n}{8} \right )+\left ( \frac{n}{4} \right )^{2}\,\sqrt{2}.................(2)$

$\text{putting the value of (1) and (2) in }\, T\left ( n \right )=4 \times T\left ( \frac{n}{2} \right )+n^{2}\,\sqrt{2}$

$T\left ( n \right )=4^{3} \times T\left ( \frac{n}{2^{3}} \right )+4^{2} \times \left ( \frac{n}{2^{2}} \right )^{2}\,\sqrt{2}+4^{1} \times \left ( \frac{n}{2^{1}} \right )^{1}\,\sqrt{2}+4^{0} \times \left ( \frac{n}{2^{0}} \right )^{2}\,\sqrt{2}$

$T\left ( n \right )=4^{k} \times T\left ( \frac{n}{2^{k}} \right )^{2}+.......+4^{2} \times \left ( \frac{n}{2^{2}} \right )^{2}\,\sqrt{2}+4^{1} \times \left ( \frac{n}{2^{1}} \right )^{2}\,\sqrt{2}+4^{0} \times \left ( \frac{n}{2^{0}} \right )^{2}\,\sqrt{2}$

$\text{Assuming base case to be } T\left ( 1 \right )=1\Rightarrow T\left ( \frac{n}{2^k} \right )=1\Rightarrow \frac{n}{2^k}=1 \Rightarrow k=\log n$

$\text{our equation becomes}$
$T\left ( n \right )=\sqrt{2} \times \left ( n^{2}+....n^{2} \right ) \text{k times}$
$T\left ( n \right )=O(n^2 \log n)$

Comments

How is $T\left ( n \right )=\sqrt{2} \times \left ( n^{2}+....n^{2} \right ) \text{k times}$

equivalent to

$T\left ( n \right )=O(n^2 \log n)$

Please explain, I did not get it

---

$T\left ( n \right )=\sqrt{2} \times \left ( n^{2}+....n^{2} \right ) \text{k times}=\sqrt{2} \times n^{2} \times k =sqrt{2} \times n^{2} \times \log n=O(n^{2} \log n)$

$\text{Note, i have ignored }\sqrt{2} \text{so i have taken upper bound i.e Big-Oh}$

---

you can use master theorem to solve this.