The first common running time treated in this section is O(n) running time. This is sometimes described as a “Linear” running time because the running increases linearly, or at the same rate as the input size. Common causes of a linear running time are loops that iterate through every item in an input or algorithms that apply a constant number of processes to each item in an input. Some examples of linear running times include finding the maximum value of an unsorted array and merging two sorted lists.
Another common run time is O(n log n). This is the run time of any algorithm that cuts an input in half, recursively solves each half and recombines them. An example of an algorithm that works like this is mergesort.
Quadratic and Cubic times are also seen a lot, due to the fact that they are the product of a loop within a loop or a loop within a loop within a loop, respectively. Quadratic time can also arise from a situation where an algorithm must perform a search over all input items and then expend constant time operating on each pair. One algorithm that uses an O(n2) running time is the Closest-pair problem, which searches through a set of pairs using a nested loop and calculates the distance between each one, tracking the minimum as it runs and resetting if necessary. Cubic time shows up in the algorithm that searches n sets to see if any are disjoint. It runs in O(n3) because it uses a nested for loop to pick pairs of sets, then a for loop inside of that to compare each item in each set for equality. In worst case, it compares every item in each of n sets, making O(n3) comparisons.
Some algorithms can run in the worst case at times that are worse than polynomial. These include running time such as exponentials and factorial growth rates. Exponentials arise in algorithms that consider all subsets, such as Independent Set, which is a computationally hard problem that requires an algorithm to find the independent set of maximum size. Factorials grow even faster than exponentials, and that class of running times includes problems that involve matching n items with n other items or arranging n items in order.
Sublinear time is a special treat that arises when an input can be “queried,” which means that there is information that can be used to help the algorithm navigate the input intelligently rather than visiting each input item individually. This is the case with the O(log n) algorithm which is able to throw away half of the input without even visiting it based on the value of the item that it visits, which will be in the middle of the remaining items.
This chapter was very straightforward and easy to read due to it discussion of running times, which I have studied before.