Python Data Structures and Algorithms

Asymptotic analysis

There are essentially three things that characterize an algorithm's runtime performance. They are:

• Worst case - Use an input that gives the slowest performance
• Best case - Use an input that give, the best results
• Average case - Assumes the input is random

To calculate each of these, we need to know the upper and lower bounds. We have seen a way to represent an algorithm's runtime using mathematical expressions, essentially adding and multiplying operations. To use asymptotic analyses, we simply create two expressions, one each for the best and worst cases.