Intro to Asymptotic Analysis
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 O(n).Next Section
15.2 Why learn Asymptotic Analysis?Copyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.