bot_vault

Big O Notation: A Visual Interactive Introduction

3 min read

Summary

Sam Who’s interactive introduction to Big O notation, covering O(1), O(log n), O(n), and O(n²) through runnable JavaScript examples and visualizations. Teaches both the theoretical definition and practical application — identifying and fixing hidden O(n²) patterns in real code like calling .indexOf() inside a loop.

透過互動式 JavaScript 範例介紹大 O 符號，涵蓋常數、對數、線性、二次四種時間複雜度，並示範如何識別和修正實際程式中隱藏的 O(n²) 問題。

Key Points

  • O(1) ≠ instant: constant time means execution time doesn’t grow with input — but it could still be slow; an O(n) algorithm can beat O(1) for small inputs
  • Big O is worst-case by default: unless stated otherwise, big O describes the worst-case scenario
  • Bubble sort = O(n²): loops n times over n elements; binary search = O(log n): eliminates half possibilities per step (≤31 guesses for 1 billion)
  • Hidden O(n²) trap: calling .indexOf() inside a for loop — .indexOf is O(n), making the outer loop O(n²). Fix: use array index directly or .entries()
  • Set lookup vs Set construction: Set.has() is O(1), but new Set(items) is O(n) — constructing per call is no improvement over array .includes()
  • Caching saves average case: memoizing factorial(n) doesn’t change worst-case O(n), but reduces average to O(1) for repeated inputs at the cost of memory

Insights

The .indexOf() inside loop anti-pattern is one of the most common hidden O(n²) bugs in production JavaScript, because modern JS engines are fast enough that it’s invisible at small scales. The article’s explicit call-out makes it memorable.

The O(1) constant clarification is important: many developers assume O(1) means “fast” and O(n) means “slow.” The correct reading is about growth rate, not absolute speed. A hash table lookup (O(1)) can be slower than a linear scan (O(n)) on a 5-element array.

Big O notation strips constant factors and lower-order terms by design. This is a deliberate tradeoff: it makes asymptotic comparisons clean but can mislead when constants are large or inputs are consistently small.

Connections

Raw Excerpt

Big O notation describes the relationship between a function’s input and its wall-clock time. It isn’t concerned with what that wall-clock time ends up being, only with how it grows.

Graph View

Backlinks