Back to Basics: Algorithmic Complexity
summary
Defines big‑O and counts loops to give concrete claims: amortized O(1) for vector::push_back with exponential growth of capacity; std::nth_element/quickselect is linear on average while median‑of‑medians guarantees worst‑case linear (spec allows quadratic worst case for practical implementers); unordered_map has average O(1) but worst case O(n); benchmarks (using QuickBench) show copying a list into a vector then sorting is faster than sorting the list; discusses actual numbers, memory locality, 64‑bit log limits, and time/space tradeoffs.
AI-written summary · about
chapters (23)
- 0:00Intro
- 0:45Why this talk
- 2:26Performance
- 11:29Quiz
- 13:28Pushback to vector
- 19:31Sorting a vector
- 25:20Unordered map
- 28:48Constant complexity
- 30:29Bubble sort
- 31:53Exponential time
- 33:21Ignore the constant
- 36:02Two calls to std
- 37:58Ranges
- 38:34Best Practices
- 39:31Break Out
- 40:11Time Out
- 41:31Microcurrencies
- 43:53Indexing
- 44:18Sorting
- 44:50Branch prediction
- 47:53Summary
- 48:58Worst Case Complexity
- 49:53Space Complexity
related talks
01h 00mBack to Basics: (Range) Algorithms in C++
53mAlgorithms Demystified
01h 00mNth pack element... - A case study
41mOverengineering is the root of all evil
57mHow to Design a Slimmer Vector of Variants in C++
05mSimple Solutions for High Performance: StaticFlatMap
32mFrom Zero To Binary Search Tree
01h 05mThe Imperatives Must Go!