A' should be asymptotically faster than A

[evinda]

Hello! (Wave)

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$.

A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} \right)+n^2$.

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

$$T(n)=7T\left( \frac{n}{2}\right)+n^2$$
$$a=7 \geq 1, b=2>1, f(n)=n^2$$

$$n^{\log_b a}=n^{\log_27}<n^{\log_2 4}=n^2$$

We see that $f(n)=O(n^{\log_b a-\epsilon})$, for example for $\epsilon=0.8$.

So, $T(n)=\Theta(n^{\log_b a})=\Theta(n^2)$

$$T'(n)=aT'\left( \frac{n}{4} \right)+n^2$$
$$b=4, f(n)=n^2$$
$$n^{\log_b a}=n^{\log_4 a}$$

• $f(n)=O(n^{\log_b a+ \epsilon})$, then $T'(n)=\Theta(n^{\log_4 a})$
  
  We want to that $A'$ is asymptotically faster that $A$, so it must be $n^{\log_4 a}<n^2 \Rightarrow n^{\log_4 a}< n^{\log_4 4^2} \Rightarrow a<16$
  $$$$
• $f(n)=\Theta(n^{\log_b a})$, then $T'(n)=\Theta(n^{\log_4 a} \log_2 n)$
  
  We want to that $A'$ is asymptotically faster that $A$, so it must be $n^{\log_4 a} \log_2 n<n^2$
  
  How can we find the $a$s, for which this inequality stands?
  $$$$
• $f(n)=\Omega(n^{\log_b a+ \epsilon})$, then $T'(n)=\Theta(f(n))=\Theta(n^2)$
  
  So, in this case, we cannot find $a$s so that $A'$ is asymptotically faster than $A$.

Is that what I have tried right? (Thinking)

 

[evinda]

Or have I done something wrong? (Thinking)