Algorithms
Big O: The Language of Efficiency
Цели урока
- Understand why measuring algorithm efficiency matters
- Learn Big O notation and its simplification rules
- Distinguish between O(1), O(log n), O(n), O(n log n), O(n²)
- Learn to determine complexity from code
Предварительные знания
- Loops in programming
In 2006, Google rejected a developer whose code worked. The reason? O(n²) instead of O(n log n). At Google's scale, that's the difference between milliseconds and hours. Big O is the language all serious developers speak.
- Google/Facebook - billions of requests, O(n²) = server death
- Games - 60 FPS = 16ms per frame, every millisecond counts
- Fintech - HFT trading, nanoseconds decide
- Interviews - first follow-up after solving: 'What's the complexity?'
History of Big O
German mathematician Paul Bachmann introduced O-notation in 1894 in his book 'Die Analytische Zahlentheorie'. Edmund Landau later popularized it, which is why it's sometimes called the 'Landau symbol'. In computer science, Big O became the standard thanks to Donald Knuth.
Why Measure Speed?
**Two developers solve the same problem.** Both solutions work. But one processes a million records in a second - the other takes an hour.
| Array size | Linear scan (operations) | Binary search |
|---|---|---|
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
**A difference of millions!** Choosing the right algorithm matters more than raw computing power.
If the input size increases by 1000×, binary search slows down by roughly:
Big O - the language of complexity
**Big O** describes how an algorithm's runtime grows as the input size increases.
Big O answers the question: **"If the input grows 10×, how much longer will this take?"**
**Key rules of Big O:**
- **Drop constants:** O(2n) = O(n), O(500) = O(1)
- **Keep the dominant term:** O(n² + n) = O(n²)
- **Worst case:** if an algorithm is sometimes fast and sometimes slow - we use the slow case
O(3n² + 100n + 500) simplifies to:
O(1) and O(n): Constant and Linear Growth
O(1) - Constant time
Runtime **does not depend** on the input size.
O(n) - Linear time
Runtime grows **proportionally** to the input size.
**Hint:** one loop over all elements = O(n)
What is the complexity of arr[len(arr) - 1]?
O(n^2): Nested Loops
**O(n²)** - runtime grows as the square of input size. Usually means nested loops.
**O(n²) is dangerous!** At n = 10,000 → 100,000,000 operations. At n = 100,000 → 10,000,000,000 - that's seconds or minutes.
An O(n²) algorithm processes 1,000 elements in 1 second. How many seconds will 10,000 elements take?
O(log n): Halving the search space
**O(log n)** - each step discards half the data. Grows very slowly: at n = 1,000,000 it takes about 20 steps.
**Where O(log n) appears:**
- Binary search
- Operations on balanced trees (BST, AVL)
- Heap lookups
- Some divide-and-conquer algorithms
**Rule of thumb:** if the data is cut **in half** each iteration - that's O(log n).
What is the maximum number of comparisons binary search needs for an array of 1,024 elements?
O(n log n): The Optimal Sort
**O(n log n)** - the gold standard for sorting. Better than O(n²), worse than O(n).
**Fact:** it has been mathematically proven that comparison-based sorting **cannot** be faster than O(n log n). It's a theoretical lower bound!
| n | O(n) | O(n log n) | O(n²) |
|---|---|---|---|
| 1,000 | 1,000 | 10,000 | 1,000,000 |
| 1,000,000 | 1,000,000 | 20,000,000 | 1,000,000,000,000 |
Merge Sort is O(n log n). Quick Sort averages O(n log n) too. Why is Quick Sort often faster in practice?
Comparing Complexities
**From fastest to slowest:**
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Index access, hash table lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Find max, single loop |
| O(n log n) | Linearithmic | Merge Sort, Quick Sort |
| O(n²) | Quadratic | Bubble Sort, nested loops |
| O(2ⁿ) | Exponential | All subsets |
| O(n!) | Factorial | All permutations |
**Goal:** aim for O(n log n) or better. O(n²) is acceptable for small n (< 1,000). O(2ⁿ) - only for very small n (< 20–30).
Which algorithm is the right choice for processing 1 million records?
Big O Cheat Sheet
- Big O - how runtime grows as data grows
- O(1) - constant, O(n) - linear, O(n²) - quadratic
- O(log n) - halving each step (binary search)
- O(n log n) - optimal sorting
- Nested loops → multiply: O(n) × O(n) = O(n²)
- Drop constants and lower-order terms
What's Next
With algorithm measurement understood, the next step is recognizing that besides time, memory matters too.
- Space Complexity — Time vs Memory
- O(n²) Sorts — Bubble, Selection, Insertion
- Binary Search — O(log n) in practice
Вопросы для размышления
- Consider a piece of code written recently - a loop, a search, a sort. What is its Big O complexity? Is there a way to improve it by one class (for example, from O(n²) down to O(n log n))?
Связанные уроки
- prog-07-loops — Loops are the primary construct that determines algorithmic complexity
- alg-02-space — Next topic: space complexity as a complement to time complexity
- ds-01-arrays — First practical application of Big O: array operations
- calc-01-sequences — Mathematics of function growth is the direct theoretical basis of Big O notation
- comp-01-intro