Essential Big O for JavaScript Developers
summary
Claims that Big O ignores hardware and JIT and instead measures steps versus input size and demonstrates that with concrete examples: a string search runs linear in the worst case, binary search runs logarithmic, a cached lookup yields amortized constant time. Shows selection sort as quadratic, explains exponential blowup with traveling salesman, and demonstrates array append/remove costs in JavaScript including that JS arrays are objects so some operations are not true contiguous-array constant time.
AI-written summary · about
chapters (20)
- 0:00Intro
- 1:05Why do we talk about Big O?
- 1:56How do we talk about speed?
- 2:42The pragmatic (and correct) answers
- 3:54How fast is it?
- 4:22Can we do a little better?
- 4:40Same complexity class: linear
- 5:14Can we change the complexity?
- 6:40Logarithmic complexity
- 7:34Silly Assumptions
- 8:04Constant complexity
- 8:49Other O(1) Operations
- 9:40The most common complexities
- 10:32Quadratic complexity
- 11:04Quadratic Example: Selection Sort
- 12:36Exponential Complexity
- 13:55Combining Complexities
- 15:21Amortization
- 18:09Other Links
- 18:31Quiz 2: Guess the complexity
related talks
29mExtreme JavaScript Performance
20mJavaScript for Competitive Programming
36mDear JavaScript...
32mFrom Zero To Binary Search Tree
27mThe Life of a JavaScript Feature in V8 ft. TypedArrays
46mHow much performance can you get out of JavaScript?
55mJavaScript the Grumpy Parts
46mMeasuring the True Cost of Abstractions in JavaScript