CODEWITHSUNDEEP
algorithmasymptotic-complexity
sauravism
sauravism

Reputation: 9

Need help Asymptotic Analysis

In the Asymptotic analysis, we always talk about input sizes larger than a constant value. It might be possible that those large inputs are never given to your software and an algorithm which is asymptotically slower, always performs better for your particular situation. So, you may end up choosing an algorithm that is Asymptotically slower but faster for your software. What does it mean?

Upvotes: 0

Views: 66

Answers (1)

Afshin
Afshin

Reputation: 9173

For what constant value means in your context, compare these 2 algorithms' asymptotic analysis results:

Algorithm A -> O(5*n^2)
Algorithm B -> O(2^n)

Now for understanding better, check how they increase:

n | Algorithm A | Algorithm B
1 | 5           | 2
2 | 20          | 4
3 | 40          | 9
4 | 90          | 16
5 | 125         | 32
6 | 180         | 64
7 | 245         | 128
8 | 320         | 256
9 | 405         | 512 <-- Threshold
10| 500         | 1024

You can think of these numbers as time spent for running algorithm and lower numbers means quicker algorithm. As you see, when n<=8 numbers for Algorithm A is bigger than Algorithm B. So if your input set is too small, then you can use Algorithm B and get better results. But if your input gets bigger, in this case n>=9, results of Algorithm B will become worse than Algorithm A. So for bigger inputs, Algorithm A works better. In your question context, Constant value means a number like 9 which create this threshold for comparing algorithms.

As a side note, When you Asymptotically analyze an algorithm, there is always a constant value such as C multiplied in your analysis result, e.g. O(C*n^2). This constant value normally have a significant effect on selecting what algorithm is more suitable if your input data is small. Just don't mistake this constant value with the one in your question context.

Upvotes: 1

Related Questions