There are a number of possible ways we can look at the time complexity of an algorithm:
Worst Case Analysis
- Upper bound on the running time of an algorithm
- The case where the maximum number of operations are preformed
Average
- Take all possible inputs and calculate the mean
- Difficult in practice
- Can be predicted with normal distributions, etc
Best
- Lower bound on running time of an algorithm
- Must know what case causes the minimum number of operations to be performed
Note
See Algorithms and Data Structures 1 for more information.