Look Ma, I Know My Algorithms!
summary
Counts unordered pairs in a large integer array whose sums fall between -100 and 100, comparing naive O(n^2) pairwise combinations with faster algorithms: an O(n log n) approach (likely via sorting and two‑pointer or binary search) and an O(n) linear solution that reduces runtime from hours to seconds on very large inputs. Discusses Ruby-specific performance pitfalls: some collection helpers conceal O(n) costs so nested use can become quadratic, and CPU‑bound work is limited by Ruby’s global interpreter lock.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:51Problem definition
- 4:42Algorithmic order
- 8:11Algorithmic orders
- 10:22Concurrency vs parallelism
- 13:54Efficient algorithms vs concurrency
- 14:59Ruby performance pitfalls
- 17:27Liquid abstractions
related talks
37m"Algorithms" is Not a Four-Letter Word
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems
05mInfinities: More Than One
43mWhat Every Programmer Should Know about How CPUs Work
01h 01mComplexity and Algorithmic Game Theory I
20m(Almost) Perfect Discrete Iterative Load Balancing
01h 01mExact Algorithms from FPT Algorithms