MHB A' is asymptotically faster than A

[evinda]

Hello! (Wave)

The recurrence relation $T(n)=7T\left( \frac{n}{2} \right)+ n^2$ describes the running time of an algorithm $A$.
A competing algorithm $A'$ has a running time of $T'(n)=aT'\left( \frac{n}{4}\right)+n^2$.
What is the largest integer value for $a$ such that $A'$ is asymptotically faster than $A$ ?

$$
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,
$$
$a = 49$, $b = 4$, and $f(n) = \frac{11}{4}n^2$

$n^{\log_b a}=n^{\log_4{49}}>n^2$

$f(n)=\Omega(n^{\log_b a+ \epsilon})$ for $\epsilon=0.8>0$.

So from the case 1 of the master theorem we conclude that $T(n) \in \Theta\left(n^{\log_4 49}\right)$.

If we assume that the initial values of the two recurrence relations are the same then we see that $T(n) \geq T'(n)$ if $a \leq 49$.$$
T'(n) = a T'\left(\frac{n}{4}\right) + n^2.
$$

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

If $a > 16$ then $\log_4 a>2$.

Then from the case case 1 of the master theorem we have that
$$
T'(n) \in \Theta\left(n^{\log_4 a}\right).
$$$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$.

So can we say that the greatest value for $a$ so that $A'$ is asymptotically faster than $A$ is $49$ or do we have to say that for $a=49$ the two algorithms have the same speed and the largest value for $a$ so that $A'$ is asymptotically faster than $A$ is $48$? (Thinking)

 

[evinda]

Could we also say the following? (Thinking)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$.

 

[I like Serena]

Hi! (Smile)

So can we say that the greatest value for $a$ so that $A'$ is asymptotically faster than $A$ is $49$ or do we have to say that for $a=49$ the two algorithms have the same speed and the largest value for $a$ so that $A'$ is asymptotically faster than $A$ is $48$? (Thinking)

I'd say the latter.
And I wouldn't say "the same speed", but "the same asymptotical speed". (Nerd)

 

[evinda]

Hi! (Smile)
I'd say the latter.
And I wouldn't say "the same speed", but "the same asymptotical speed". (Nerd)

Saying the latter, I don't have to say anything about asymptotical speed, do I? (Thinking)
And something else... Do we also have to check the case when $\alpha \leq 16$?

 

[I like Serena]

Could we also say the following? (Thinking)

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

Seems fine to me. (Smile)

Saying the latter, I don't have to say anything about asymptotical speed, do I? (Thinking)
And something else... Do we also have to check the case when $\alpha \leq 16$?

You're supposed to say something about "faster asymptotical speed". There is no need to say something about "the same asymptotical speed".

The algorithm will only be even faster in the case $\alpha \leq 16$, so there is no need to check it explicitly.
You might mention that though. (Nerd)

 

[evinda]

Seems fine to me. (Smile)

(Smile)

You're supposed to say something about "faster asymptotical speed". There is no need to say something about "the same asymptotical speed".

The algorithm will only be even faster in the case $\alpha \leq 16$, so there is no need to check it explicitly.
You might mention that though. (Nerd)

If $\alpha=16$ the solution of the recurrence relation will be $T(n)=\Theta(n^2 \lg n)$ and if $\alpha<16$ the solution of the recurrence relation will be $T(n)=\Theta(n^2)$, right?

If I want to mention it, what could I say? (Thinking)

 

[I like Serena]

If $\alpha=16$ the solution of the recurrence relation will be $T(n)=\Theta(n^2 \lg n)$ and if $\alpha<16$ the solution of the recurrence relation will be $T(n)=\Theta(n^2)$, right?

I haven't checked it, but that looks about right. (Smile)

If I want to mention it, what could I say? (Thinking)

I'd mention what I just wrote: "The algorithm will only be even faster in the case α≤16, so there is no need to check it explicitly." (Nerd)

 

[evinda]

I'd mention what I just wrote: "The algorithm will only be even faster in the case α≤16, so there is no need to check it explicitly." (Nerd)

At which point could I mention it? (Thinking)

 

[I like Serena]

At which point could I mention it? (Thinking)

Just before you state the conclusion.
It shows you've considered all possible cases. (Wasntme)

 

[evinda]

Just before you state the conclusion.
It shows you've considered all possible cases. (Wasntme)

Nice! (Happy)

After writing the recurrence relation, can I just write $\alpha \geq 1$ in order to apply the Master theorem or do I have to write that I assume that it is like that? (Thinking)

 

[I like Serena]

Nice! (Happy)

After writing the recurrence relation, can I just write $\alpha \geq 1$ in order to apply the Master theorem or do I have to write that I assume that it is like that? (Thinking)

I would write "If we assume $\alpha \geq 1$, we can apply the Master Theorem", and then apply it.

At the end, before the conclusion, I would mention that with $\alpha < 16$ the algorithm will only be faster.
That covers all cases that were not verified explicitly, including the assumption that $\alpha \geq 1$. (Wasntme)

 

[evinda]

I would write "If we assume $\alpha \geq 1$, we can apply the Master Theorem", and then apply it.

A ok... (Nod)

At the end, before the conclusion, I would mention that with $\alpha < 16$ the algorithm will only be faster.
That covers all cases that were not verified explicitly, including the assumption that $\alpha \geq 1$. (Wasntme)

Do I also have to say then something for the case $\alpha=16$? (Thinking)

 

[I like Serena]

A ok... (Nod)

Do I also have to say then something for the case $\alpha=16$? (Thinking)

Oh, I meant $\alpha \le 16$.

 

[evinda]

Oh, I meant $\alpha \le 16$.

For $16<\alpha<49$ we have that $T'(n)=\Theta(n^{\log_b {\alpha}})$ and $^2<n^{\log_4 a}<n^{\log_4{49}} \approx n^{2.8}$, right?
For $\alpha=16$ the solution of the recurrence relation is $T'(n)=\Theta(n^2 \lg n)$.
So couldn't it be that the latter isn't less than the former? Or am I wrong?

 

[I like Serena]

For $16<\alpha<49$ we have that $T'(n)=\Theta(n^{\log_b {\alpha}})$ and $^2<n^{\log_4 a}<n^{\log_4{49}} \approx n^{2.8}$, right?
For $\alpha=16$ the solution of the recurrence relation is $T'(n)=\Theta(n^2 \lg n)$.
So couldn't it be that the latter isn't less than the former? Or am I wrong?

No. If an algorithm takes less steps to execute, it will always be faster.
And indeed, as you can see $n^2 \lg n$ is asymptotically less than $n^{2.8}$.
It's even stronger: the lower $\alpha$ is, the lower $T'(n)$ is, all other things being the same. (Wasntme)

 

[evinda]

No. If an algorithm takes less steps to execute, it will always be faster.
And indeed, as you can see $n^2 \lg n$ is asymptotically less than $n^{2.8}$.
It's even stronger: the lower $\alpha$ is, the lower $T'(n)$ is, all other things being the same. (Wasntme)

I see... Thank you very much! (Party)