Asymptotic analysis of an algorithm refers to defining the mathematical foundation/framing of its run time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.
• It refers to computing the running time of any operation in mathematical units of computation
Based on the three asymptotic notations of Time Complexity there are three cases to analyze an algorithm:
Worst Case Analysis:
In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed. Most of the time, we do worst-case analyses to analyze algorithms.
• In the worst analysis, we guarantee an upper bound on the running time of an algorithm which is good information.
Best Case Analysis:
In the best-case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case that causes a minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location.
• The number of operations in the best case is constant (not dependent on n).
Average Case Analysis:
In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs. We must know (or predict) the distribution of cases.
• The average case analysis is not easy to do in most practical cases and it is rarely done.
