This Chapter went into further detail about some common running times, including:

Linear time O(n) This running time is at most a constant factor times the size of the input. Common problems that have this running time include computing the maximum and merging two sorted lists.

O(nlogn) Time

This is the running time of any algorithm that splits its inputs into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time.

Quadratic Time

Example for this: you're given a certain number of points on a plane, and you want to find which pair is closest together. Each time you measure a line between two points, you can skip out on doing it in the opposite direction.

Cubic Time

From what I can tell, only happens with triple-nested loops, each of which operates at a runtime of O(n). They compound to make the runtime cubic.

O(n^k) Time

We obtain a runtime of O(n^k) for any constant k when we search over all subsets of size k.

Bigger than Polynomial

Things that are order O(n!), such as finding the number of ways to match up n items with n other items, are even more costly than functions of an order like O(n^2)

Smaller than Linear

Binary search algorithm is O(logn). This runtime arises when we're dealing with an algorithm that does a constant amount of work in order to throw away a constant fraction of the inputs.

This chapter was very straightforward. The only algorithms it detailed were to demonstrate runtimes of simple algorithms such as those mentioned above. I don't have any questions about it and I think learning this will just be very straightforward and memorization-focused.

Brief summary of the section ~1 paragraph of about 5-10 sentences per section feel free to write more if that will help you Include motivations for the given problem, as appropriate For algorithms, brief sketch of algorithm, intuition, and implementation Include runtime for algorithms Questions you have about motivation/solution/proofs/analysis Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa) Anything that you want to remember, anything that will help you Say something about how readable/interesting the section was on scale of 1 to 10