Stage 1 · Code
Programming Foundations
Time & Space Complexity
Big-O notation, best/average/worst case, and complexity classes.
Big-O Notation Basics
Big-O describes the upper bound of an algorithm's growth rate as input size increases. It ignores constants and lower-order terms, focusing on the dominant factor.
Common Complexity Classes
| Notation | Name | Typical Algorithm | n=1000 ops |
|---|---|---|---|
| O(1) | Constant | Hash lookup | 1 |
| O(log n) | Logarithmic | Binary search | 10 |
| O(√n) | Square root | Trial division | 32 |
| O(n) | Linear | Array scan | 1,000 |
| O(n log n) | Linearithmic | Merge sort | 10,000 |
| O(n²) | Quadratic | Bubble sort | 1,000,000 |
| O(2ⁿ) | Exponential | Subsets/backtracking | ~10³⁰¹ |
| O(n!) | Factorial | Permutations | ~∞ |
Best, Average, Worst Case
Algorithms can have different complexities depending on input:
- Best case: Optimal input (e.g., already sorted array for insertion sort: O(n)).
- Average case: Expected input distribution (e.g., quicksort: O(n log n)).
- Worst case: Adversarial input (e.g., quicksort with sorted input: O(n²)).
Always state worst-case complexity unless asked otherwise. Mention average case if it differs significantly. Be prepared to explain why.
Space Complexity
Space complexity measures auxiliary space (extra space beyond input). Don't count input space unless specified.
Amortized Analysis
Amortized cost averages operations over a sequence. Dynamic array append is O(1) amortized: most appends are O(1), occasional resize is O(n), but averaged over many operations it's O(1).
Go's slice append is amortized O(1). The underlying array doubles when capacity is exceeded. This is why pre-allocating with make([]int, 0, n) can avoid resizes when you know the approximate size.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.