[Math] Which is the greatest integer value of $a$, for which $A’$ is asymptotically faster than $A$

algorithmsasymptoticscomputational complexitydiscrete mathematics

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's what I have tried right?

EDIT:

Could we also say it as follows?

We have the recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ and the solution is $T(n)=\Theta(n^{\log_{4}{49}})$.
We also have the recurrence relation $T'(n)=\alpha T'\left( \frac{n}{4} \right)+n^2$.

$a=\alpha, b=4, f(n)=n^2$

$n^{\log_b a}=n^{\log_4 \alpha}$
For $\alpha>16$, $f(n)=O(n^{\log_b{\alpha}}- \epsilon), \epsilon>0$

So for $\alpha>16$: $T'(n)=\Theta(n^{\log_4{\alpha}})$

So that $A'$ is asymptotically faster than $A$, it has to hold $n^{\log_4{\alpha}}< n^{\log_4{49}} \Rightarrow \log_4{\alpha}<\log_4{49} \Rightarrow \alpha<49$

So the greatest value for $\alpha$ so that $A'$ is asymptotically faster than $A$ is $48$.

Best Answer

There are some missteps in your application of the master theorem.

First

$$ T(n) = 7\left[ 7T\left(\frac{n}{4}\right) + \frac{1}{4}n^2\right] + n^2 = 49 T\left(\frac{n}{4}\right) + \frac{11}{4}n^2, $$

so let's call $a = 49$, $b = 4$, and $f(n) = \frac{11}{4}n^2$. Clearly $f(n) \in O(n^2)$, so let's also call $c = 2$. Then

$$ 2 = c < \log_b a = \log_4 49 \approx 2.81, $$

so we can apply case 1 of the master theorem (according to wikipedia) to find that

$$ T(n) \in \Theta\left(n^{\log_4 49}\right). $$

Further this form of the recurrence allows us to see immediately that $T(n) \geq T'(n)$ if $a \leq 49$, presuming the initial values are the same. (Why? This is important.) $\tag{$\dagger$}$

Now let's look at the recurrence for $T'$, which is

$$ T'(n) = a T'\left(\frac{n}{4}\right) + n^2. $$

We'll re-use the variable names from before, but in this case set $a = a$, $b = 4$, and $f(n) = n^2$. Again $f(n) \in O(n^2)$, so $c = 2$. If $a > 16$ then $2 = c < \log_4 a$, so case 1 of the master theorem again tells us that

$$ T'(n) \in \Theta\left(n^{\log_4 a}\right). $$

Of course

$$ n^{\log_4 49} \in o\left(n^{\log_4 a}\right) $$

if $a > 49$, so we conclude that $T(n) \in o\Bigl(T'(n)\Bigr)$ if $a > 49$. $\tag{$\ddagger$}$

Combining $(\dagger)$ and $(\ddagger)$, we can conclude that $49$ is the least integer value of $a$ for which algorithm $A'$ is asymptotically faster than algorithm $A$.

Related Question