Doing an asymptotic analysis means figuring out the upper or lower bound for the growth of an algorithm’s running time(i.e. how fast the algorithm runs) as the algorithm’s input size increases.
Here’s a graph to visualize:
Confused about what
O(n)means? We will cover it in a later section. Let’s talk about this graph.
Why is the running time not in terms of actual time (like 12 secs)? Well, different computers have different performance speeds, so in order to have a standard for which all computers share, we look at the running time in terms of n how many operations the algorithm does.
In the graph, you can see how the number of operations of an algorithm (y-axis) increases as the input size
n(x-axis) increases. The growth of our algorithm is the green line while the growth of the upper bound is the red line. We can say in this case, our algorithm is upper bounded by n running time, or