A' is asymptotically faster than A

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the asymptotic comparison of the running times of two algorithms, $A$ and $A'$, defined by their respective recurrence relations. Participants explore the conditions under which $A'$ is asymptotically faster than $A$, focusing on the parameter $a$ in the recurrence of $A'$ and its implications on the growth rates of the algorithms.

Discussion Character

  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose that for $A'$ to be asymptotically faster than $A$, the parameter $a$ must be less than 49, suggesting that $a = 48$ is the largest integer value for which this holds.
  • Others argue that if $a = 49$, the two algorithms have the same asymptotic speed, thus implying that $A'$ is not faster in that case.
  • A later reply questions whether the case when $a \leq 16$ should be considered, as it might affect the asymptotic comparison.
  • Participants discuss the implications of different values of $a$, noting that for $16 < a < 49$, $T'(n)$ grows faster than $T(n)$, but for $a = 16$, $T'(n)$ is $\Theta(n^2 \log n)$, which raises questions about its comparison with $T(n)$.
  • There is a suggestion that the algorithm will only be faster when $a < 16$, but this is not explicitly verified in the discussion.
  • Some participants emphasize the importance of stating assumptions, such as $\alpha \geq 1$, when applying the Master theorem.

Areas of Agreement / Disagreement

Participants express differing views on the largest value of $a$ for which $A'$ is asymptotically faster than $A$. While some support the idea that $a$ must be less than 49, others highlight the need to clarify the implications of $a = 49$ and the conditions under which $A'$ might still be considered faster. The discussion remains unresolved regarding the treatment of cases when $a \leq 16.

Contextual Notes

There are limitations in the discussion regarding the assumptions made about the initial conditions of the recurrence relations and the implications of different ranges of $a$. The relationship between the growth rates of the algorithms is not fully resolved, particularly for the case of $a = 16$.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Technology news on Phys.org
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$.
 
Hi! (Smile)

evinda said:
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)
 
I like Serena said:
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$? :confused:
 
evinda said:
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)
evinda said:
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$? :confused:

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)
 
I like Serena said:
Seems fine to me. (Smile)

(Smile)

I like Serena said:
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)
 
Last edited:
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
At which point could I mention it? (Thinking)

Just before you state the conclusion.
It shows you've considered all possible cases. (Wasntme)
 
  • #10
I like Serena said:
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)
 
  • #11
evinda said:
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)
 
  • #12
I like Serena said:
I would write "If we assume $\alpha \geq 1$, we can apply the Master Theorem", and then apply it.
A ok... (Nod)

I like Serena said:
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)
 
  • #13
evinda said:
A ok... (Nod)

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

Oh, I meant $\alpha \le 16$. :o
 
  • #14
I like Serena said:
Oh, I meant $\alpha \le 16$. :o

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? :confused:
 
  • #15
evinda said:
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? :confused:

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)
 
  • #16
I like Serena said:
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)
 

Similar threads

MHB A' should be asymptotically faster than A
  • · Replies 1 ·
Replies
1
Views
1K
MHB Representation of signed integers of base B
  • · Replies 17 ·
Replies
17
Views
2K
Graduate Show positivity and boundedness of a non-linear system
  • · Replies 2 ·
Replies
2
Views
1K
Python Does this python script match the math?
  • · Replies 15 ·
Replies
15
Views
2K
Python Thermal lattice Boltzmann model ignoring source term -- python code help please
  • · Replies 1 ·
Replies
1
Views
3K
Python Finding a local max/min of a function in Python
  • · Replies 7 ·
Replies
7
Views
5K
Fourier series of this scale and shift of triangle wave
  • · Replies 1 ·
Replies
1
Views
2K
MHB Master Theorem-Relation of the two functions
  • · Replies 2 ·
Replies
2
Views
1K
Finding a periodic solution to ODE
  • · Replies 16 ·
Replies
16
Views
2K
Graduate Dirac's "comprehensive action principle" -- independent equations
  • · Replies 1 ·
Replies
1
Views
870