AI summary by TwinMind
Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation
Tom Scott
9m 45s
Personal Anecdote - Work Experience Photo Search System
- Age 15 work experience at unnamed company (British equivalent of internship)
- Task: categorize hundreds/thousands of scanned historical photos with arbitrary filenames
- Attempted to build search system like Yahoo/Google to show off
- Simple approach: loop through descriptions, count word matches, sort by match count
- System worked until ~50 photographs, became slow at 100+
- Spent more time fixing code than doing assigned job
- Problem: used inefficient algorithm without understanding Big O notation
Big O Notation Fundamentals
- Definition: single expression indicating algorithm performance as input size increases
- Origins: German mathematicians (late 19th century), popularized by Donald Knuth (1970s)
- Purpose: compare algorithms in "big picture" sense for scalability
- Key insight: distills algorithm down to growth rate expression
Common Big O Classifications
- O(1) - Constant: same processing time regardless of input size
- Example: return first item in list
- O(n) - Linear: processing time increases steadily with input
- Example: perform one operation on each list item
- O(n²) - Quadratic: processing time increases with square of input
- Double input = quadruple runtime
Sorting Algorithm Examples and Analysis
Bubble Sort
- Method: compare adjacent pairs, swap if wrong order, repeat until sorted
- Performance: O(n²) - terrible efficiency
- Must check every block on every pass
- 10 blocks = 10 operations × 10 times
- 100 blocks = 100 operations × 100 times
Insertion Sort
- Method: take each item, move toward start until correct position found
- Performance: O(n²) but typically faster than bubble sort in practice
- Similar to sorting playing cards by hand
- Same Big O as bubble sort but shorter actual runtime
Quicksort
- Method: choose pivot, partition smaller/larger items, recursively sort partitions
- Worst case: O(n²)
- Average case: O(n log n) - significantly better performance
- Uses divide-and-conquer approach
Bogosort (Joke Algorithm)
- Method: randomize list, check if sorted, repeat until sorted
- Performance: O((n+1)!) - factorial time complexity
- Designed as intentionally terrible algorithm
Key Big O Principles
- Program's overall Big O determined by worst-performing component
- Example: 10 linear operations + 1 quadratic operation = O(n²) overall
- Big O is approximation/guide, not exact performance measure
- Focus on scalability trends rather than precise timing
Lesson Learned - Practical Application
- Original problem: should have used simple Word document with Ctrl+F search
- Better solution characteristics:
- Doesn't break with OS updates
- Anyone can update by typing
- Still accessible today
- Meets actual user needs
- Key insight: best solution isn't always fastest/smartest, but what works long-term for users
- Mistake: prioritized showing off technical skills over solving actual problem
