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
nnumber of operations as
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 terms