- #1
evinda
Gold Member
MHB
- 3,741
- 0
Hello! (Wave)
I want to use the master theorem, in order to find the exact asymptotic solution of $S(m)=4S \left ( \frac{m}{2}\right )+m^3 \sqrt{m}$.
$$a=4 \geq 1, b=2>1, f(m)=m^3 \sqrt{m}$$
$$m^{\log_b a}=m^{\log_2{2^2}}=m^2$$
$$f(m)=m^{3+\frac{1}{2}}=m^{\log_b a+ \frac{3}{2}}$$
Thus, $f(m)=\Omega(m^{\log_b a+ \epsilon}), \epsilon=\frac{3}{2}$
$$af \left ( \frac{m}{b}\right )=4 \left (\frac{m}{2} \right )^3 \sqrt{\frac{m}{2}}=4 \frac{m^3}{8} \frac{\sqrt{m}}{\sqrt{2}}=\frac{1}{2 \sqrt{2}} m^3 \sqrt{m} \leq c f(m), \forall c \in [\frac{1}{2 \sqrt{2}},1) $$
Therefore, $S(m)=\Theta(m^3 \sqrt{m})$.
Is it right or do I have to simplify the complexity I found? (Thinking)
I want to use the master theorem, in order to find the exact asymptotic solution of $S(m)=4S \left ( \frac{m}{2}\right )+m^3 \sqrt{m}$.
$$a=4 \geq 1, b=2>1, f(m)=m^3 \sqrt{m}$$
$$m^{\log_b a}=m^{\log_2{2^2}}=m^2$$
$$f(m)=m^{3+\frac{1}{2}}=m^{\log_b a+ \frac{3}{2}}$$
Thus, $f(m)=\Omega(m^{\log_b a+ \epsilon}), \epsilon=\frac{3}{2}$
$$af \left ( \frac{m}{b}\right )=4 \left (\frac{m}{2} \right )^3 \sqrt{\frac{m}{2}}=4 \frac{m^3}{8} \frac{\sqrt{m}}{\sqrt{2}}=\frac{1}{2 \sqrt{2}} m^3 \sqrt{m} \leq c f(m), \forall c \in [\frac{1}{2 \sqrt{2}},1) $$
Therefore, $S(m)=\Theta(m^3 \sqrt{m})$.
Is it right or do I have to simplify the complexity I found? (Thinking)