MHB Recurrence Relation: Master Theorem Solution

AI Thread Summary
The discussion focuses on applying the Master Theorem to solve the recurrence relation S(m)=4S(m/2)+m^3√m. The calculations show that a=4, b=2, and f(m)=m^3√m, leading to m^log_b a=m^2. The analysis confirms that f(m) is asymptotically larger than m^log_b a, establishing that S(m)=Θ(m^3√m). Participants agree that the solution is correct without the need for further simplification.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
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)
 
Physics news on Phys.org
evinda said:
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)

Hey! (Smile)

It is right! (Nod)
 
I like Serena said:
Hey! (Smile)

It is right! (Nod)

Nice! Thanks a lot! (Smirk)
 
Back
Top