Algorithms

See CppCon 2018: Jonathan Boccara: 105 STL Algorithms in Less Than an Hour.

Secret runes

See Introsort and sorting algorithms.

Algorithm patterns

See algorithm patterns.

Big-O notation

Big-O notations is a technique to describe the complexity of an algorithm as the data set becomes larger.

Be prepared to write code. Remember your merge sort, quick sort, binary search, etc, and be able to write them cold.

Complexity name
O(1) constant
O(log n) logarithmic
O(n) linear
O(n log n)=O(log n!) linearithmic
O(n^2) quadratic
O(n^c) polynomial
O(c^n) exponential
O(n!) factorial

See the Big-O cheat sheet and time complexity

Memory access

That assumes all memory accesses cost the same, which is not a physically reasonable assumption as we scale n to infinity, and not, in practice, how real computers work. This argument extends from the observation that computers are filled with different types of memory (cache, system memory, virtual memory etc.) in different and limited quantities. Modern operating systems will position variables into these different systems automatically making memory access time differ widely as more and more memory is utilized.

References