Comparing Running times
Explore how to compare the running times of algorithms by analyzing how their time functions grow as input size increases. Understand the importance of asymptotic notation, especially big-O, and how it helps assess algorithm efficiency beyond small input sizes. This lesson equips you with the skills to evaluate and contrast algorithm performance using mathematical growth rates.
We'll cover the following...
Motivation for comparing growth of functions
Alice and Bob are trying to solve the same problem, and they both come up with different algorithms for it.
They are able to express their running times as two functions. But can they compare the two functions and see if one is better than the other?
One has a running time of time units, and the other has a running time of time units. Is the performance of both algorithms similar, or is one better than the other?
To be able to make this kind of assessment, we need to compare the two polynomials and look at how the functions grow.
Comparing how different functions grow
Let’s look at how some functions grow as the value of grows larger.