Algorithm definition is asymptotically faster
how could you tell if one algorithm is asymptotically faster than another? Let's say one equation: t (n) = 7t (n / 2) + n ^ 2, and another t (n) = aT (n / 4) + n ^ 2. how would you determine for what value of a this equation will be faster than the first.
Any help would be appreciated.
source to share
I am not an expert in algorithm performance analysis, but ...
Asymptotically, you take the largest of the two terms to determine the growth of the algorithm. So you will need to define a value for "a" which will cause the first term to grow faster than the second, but since we are also comparing this to the first equation, it should have a higher growth rate than it also. According to the main theorem, this will be where n log ba > f (n).
Using the values in your example f (n) = n 2 b = 4. So you have to solve Log 4 a> Log 27> 2 for a. Its OK. 48.5
Edit: This is not what I used as a source, but I decided to do some searches to find a subsidiary source. https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
source to share