Rules for this Course
1) We are looking at the worst-case (Note: Don’t confuse the worst case with Big-O. Worst case means the arrangement of inputs that will give you the slowest result while Big-O means the upper bound on an algorithm).
Reason: There exists best case, the average case, and many more cases, but they will take up extra time to go over that we don’t have in this course. Another reason is listed under reason for using Big-O
2) We are using Big-O
Reason: Other notations will take up extra time to go over that we don’t have in this course. Also, Big-O is the most practical. Suppose you are given a time limit for the algorithm you come up with (like in coding contests!). By analyzing using upper bounds and worst case, you make sure your algorithm is within the time limit.
3) Don’t loosely bound your algorithm (e.g. Don’t bound an algorithm that takes
n number of operations as O(n^2) or O(n^3) or so on).Reason: Although this strategy falls within the definition of upper bound, you are losing information by doing that. Like how do you compare two algorithms that are loosely bound? So, make your bound as tight as possible
4) Ignore constants and lower order terms
Reason: It makes analyzing much simpler. You may ask how is
3*O(1) + 3*O(n) and O(n) the same running time? Well, they have the same growth rate, and asymptotic analysis deals with the growth rate, not the actual running time. If you were to compare algorithms of the same growth rate, you would have to look at the constants and lower order termsPrevious Section
15.3 Asymptotic Notations - The ThreeNext Section
15.5 Running Time ExamplesCopyright © 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.