Algorithmic Complexity

Your computer processes billions of operations per second. Yet a simple nested loop can grind to a halt on 100,000 items. The bottleneck isn't your hardware — it's the growth pattern of your algorithm. Big-O notation gives you a tool to see this pattern at a glance and predict bottlenecks before they happen.

No formal math required — just a shift in how you think about "fast" and "slow."

Scaling — Why Hardware Cannot Rescue Bad Algorithms

Imagine searching for one book among n books in a library. Strategy A (linear search, O(n)): you check every book one by one — worst case n steps. Strategy B (binary search, O(log n)): the catalogue is sorted, so you halve the search space with each look. At 1,000 books: A needs up to 1,000 steps, B needs about 10. At 1,000,000 books: A needs up to 1,000,000 steps, B needs about 20.

Analogy:

Imagine searching for one book among n books in a library. Strategy A (linear search, O(n)): you check every book one by one — worst case n steps. Strategy B (binary search, O(log n)): the catalogue is sorted, so you halve the search space with each look. At 1,000 books: A needs up to 1,000 steps, B needs about 10. At 1,000,000 books: A needs up to 1,000,000 steps, B needs about 20.

Definition:

Big-O notation classifies how an algorithm's resource consumption grows with input size n. It ignores constants and focuses on the dominant term. O(1) means constant, O(log n) logarithmic, O(n) linear, O(n²) quadratic, O(2ⁿ) exponential. Developed in the late 19th century by Bachmann and Landau; Knuth popularised it as a standard tool for computer science.

The library analogy hides that binary search requires pre-sorted data — sorting itself costs O(n log n). In a real library you can scan shelves visually and skip sections, making the search richer than the pure algorithmic model.

1

Start: 1,000,000 books — check the middle

2

Eliminate half → 500,000 remaining

3

Halve again → 250,000, then 125,000 ...

4

After 10 steps: only ~1,000 books left

5

After ~20 steps: book found (out of 1 million!)

Each time you double the number of books, you need only one additional search step. That is the power of logarithmic growth.

Bubble Sort (O(n²))

At n = 100,000: ~10 billion comparisons. Compares adjacent elements and swaps them. Simple, but extremely slow on large datasets.

Merge Sort (O(n log n))

At n = 100,000: ~1.7 million comparisons. Recursively splits, sorts, and merges. A thousand times faster on large data.

Faster hardware is just a constant factor. With exponential growth, a computer that is twice as fast lets you process only one more unit of n. The growth rate dominates any constant.

A supercomputer processes 10 billion operations per second. With a linear algorithm O(n) at n = 1 billion: done in 0.1 seconds. With an exponential algorithm O(2ⁿ)? A completely different story.

n = 50:  2⁵⁰ ≈ 1.1 × 10¹⁵ operations → hours
n = 100: 2¹⁰⁰ ≈ 1.27 × 10³⁰ operations
→ Longer than the age of the universe (~4.3 × 10¹⁷ seconds)

This is why exponential algorithms become impractical at surprisingly small n — no matter how fast your hardware is.

O(n) vs. O(n²) — The Four Everyday Classes

O(1) — Constant Work doesn't change with n. Example: accessing an array element by index.

O(log n) — Logarithmic Grows extremely slowly. Doubling n = one more step. Example: binary search.

O(n) — Linear Doubling n = double the work. Example: scanning through a list once.

O(n²) — Quadratic Doubling n = four times the work. Example: comparing all pairs.

Imagine a dinner party. Peeling potatoes (O(n)): one per guest — double the guests, double the potatoes. Handshakes (O(n²)): every guest shakes hands with every other guest.

Guests   Potatoes    Handshakes
    4          4              6
   10         10             45
  100        100          4,950
1,000      1,000        499,500

Ten times more guests: 10× more potatoes, but ~100× more handshakes. That is the difference between linear and quadratic growth.

In reality, you can peel potatoes in parallel and greet guests in groups — in CS, this corresponds to designing better algorithms that avoid the all-pairs pattern.

For small n (e.g. 20 items), a simple O(n²) algorithm is often faster than a complex O(n log n) algorithm with high overhead. Big-O becomes critical when n can grow unpredictably — user data, network traffic, database tables.

Real standard libraries use hybrid strategies: for small arrays, a simple O(n²) algorithm like Insertion Sort is used (less overhead). Only for larger datasets does the library switch to an asymptotically better O(n log n) algorithm like Merge Sort. The best of both worlds.

Interactive: Compare Growth Patterns

Move the slider to vary the input size n from 1 to 1,000. Watch how differently O(log n), O(n), and O(n²) grow — especially beyond n = 100, the gap between linear and quadratic growth becomes dramatic.

Input size n = 100

11000

O(log n)6.6

O(n)100

O(n log n)664

O(n²)10.000

Moderate Input

At n=100, the difference becomes visible: O(n²) requires 10.000 operations, while O(n) needs only 100. O(log n) needs just 6.6 — that's 15x less than O(n).

Ratio to O(n)

Complexity	Operations	Factor vs. O(n)
O(log n)	6.6	15x faster
O(n)	100	1x (Reference)
O(n log n)	664	6.6x slower
O(n²)	10.000	100x slower

Interactive: The Sorting Race

Two sorting methods compete on the very same data. Predict who finishes first and feel why O(n log n) pulls further ahead as n grows.

Time vs. Space — The Trade-Off

Imagine driving to a new destination. Option A: at every intersection, you pull out the map and compass and calculate the route from scratch — O(n) time, no memory. Option B: you calculate the route once beforehand, write it on a note, and at each intersection you just read the next turn — O(1) time per intersection, O(n) memory for the note. A small memory investment (the route note) saves you computation time at every intersection.

Analogy:

Imagine driving to a new destination. Option A: at every intersection, you pull out the map and compass and calculate the route from scratch — O(n) time, no memory. Option B: you calculate the route once beforehand, write it on a note, and at each intersection you just read the next turn — O(1) time per intersection, O(n) memory for the note. A small memory investment (the route note) saves you computation time at every intersection.

Definition:

Algorithms consume two resources: time (computation steps) and space (memory). The time-space trade-off means you can often invest memory to save time (caching, indexing, memoization) — or save memory at the cost of recomputation. Example: naive Fibonacci recursion is O(2ⁿ) time; with memoization it becomes O(n) time at O(n) space.

In reality, trade-offs are often non-linear: a small cache can speed up access by a factor of 1,000. Some problems, however, have exponential space requirements where more memory doesn't help.

Naive Recursion vs. Memoization

Naive Recursion — O(2ⁿ) fib(50): ~2⁵⁰ ≈ 1.1 quadrillion function calls. Each call recomputes everything — hours to days of computation.

Memoization — O(n) fib(50): only 49 actual computations + 49 stored values. Result available instantly — that is the power of a memory investment.

Instead of quadrillions of calls, only 49 actual computations. A small memory investment (49 values) buys an exponential speedup.

Large language models use the same trade-off: full precision (32 bits) needs lots of memory but delivers maximum accuracy. Quantisation (8 or 4 bits) halves or quarters memory use and speeds up inference — at a controlled quality cost. Here, memory space is traded for mathematical precision — the Big-O class does not change, but the hardware load is massively reduced.

Deliberate memory use (caches, indices, precomputed tables) is one of the most powerful optimisation techniques. The goal is not minimal memory but the right balance — invest memory where it saves disproportionate computation time.

When you learn about Python dictionaries in later articles, you will see exactly this trade-off again: dictionaries invest memory in hash tables to speed up access from O(n) to O(1).

Big-O measures growth shape, not clock time. A faster computer only delays the problem — it never solves a bad growth rate.
Four classes cover 90% of everyday thinking: O(1) constant, O(log n) logarithmic, O(n) linear, O(n²) quadratic.
Time and space are two currencies you trade against each other. Caching, memoization, and indexing are deliberate memory investments to buy speed.

What does Big-O notation describe?

How fast a computer's processor is

The growth pattern of an algorithm's resource usage as input size increases

The exact number of seconds an algorithm takes

Which programming language is being used

1. What does Big-O notation describe?

☐ A) How fast a computer's processor is
☐ B) The growth pattern of an algorithm's resource usage as input size increases
☐ C) The exact number of seconds an algorithm takes
☐ D) Which programming language is being used

2. You double the number of items in a list. An algorithm now takes four times as long. What is its Big-O class?

☐ A) O(1)
☐ B) O(n)
☐ C) O(n²)
☐ D) O(log n)

3. A naive Fibonacci function calls itself billions of times for fib(50). Which technique reduces this to only 49 real computations?

☐ A) Using a faster computer
☐ B) Writing the code in a faster language
☐ C) Memoization — storing already computed results
☐ D) Using shorter variable names

4. An O(n²) sorting algorithm is sometimes preferred over an O(n log n) algorithm. In which situation is this reasonable?

☐ A) When the dataset has millions of entries
☐ B) When n is small (e.g. 20 elements) and the simpler algorithm has less overhead
☐ C) When the computer has a fast processor
☐ D) When memory is unlimited

Answer Key: 1) B · 2) C · 3) C · 4) B

Checkpoint: Do You Understand Big-O?

Why does an exponential algorithm fail even on the world's fastest supercomputer once n grows large enough?
You double the input data. An algorithm now takes four times as long. Which Big-O class is this?
Naive Fibonacci recursion is extremely slow. Which technique reduces the runtime from O(2ⁿ) to O(n), and what does it cost?

Algorithmic Complexity

Scaling — Why Hardware Cannot Rescue Bad Algorithms

Big-O Notation

Analogy:

Definition:

Binary Search: Step by Step

Misconception: A Faster Processor Solves the Problem

Deep Dive: The Supercomputer Loses

O(n) vs. O(n²) — The Four Everyday Classes

Potatoes vs. Handshakes

Misconception: O(n²) Is Always Bad

Deep Dive: Hybrid Sorting in Practice

Interactive: Compare Growth Patterns

Ratio to O(n)

Interactive: The Sorting Race

Time vs. Space — The Trade-Off

Time-Space Trade-Off

Analogy:

Definition:

Fibonacci: Exponential vs. Memoized

Naive Recursion vs. Memoization

In AI: LLM Optimisation

Misconception: Less Memory Is Always Better

Key Takeaways

Quiz: Big-O Notation

What does Big-O notation describe?

Checkpoint: Do You Understand Big-O?

Scaling — Why Hardware Cannot Rescue Bad Algorithms

Big-O Notation

Analogy:

Definition:

Binary Search: Step by Step

Misconception: A Faster Processor Solves the Problem

Deep Dive: The Supercomputer Loses

O(n) vs. O(n²) — The Four Everyday Classes

Potatoes vs. Handshakes

Misconception: O(n²) Is Always Bad

Deep Dive: Hybrid Sorting in Practice

Interactive: Compare Growth Patterns

Ratio to O(n)

Interactive: The Sorting Race

Time vs. Space — The Trade-Off

Time-Space Trade-Off

Analogy:

Definition:

Fibonacci: Exponential vs. Memoized

Naive Recursion vs. Memoization

In AI: LLM Optimisation

Misconception: Less Memory Is Always Better

Key Takeaways

Quiz: Big-O Notation

What does Big-O notation describe?

Checkpoint: Do You Understand Big-O?

Related Content

Article

What Is an Algorithm?

Linear Data Structures

Recursion

Lists and Dictionaries

Data Structures II (Hierarchical & Networked)

Data Structures III (Key-Based)

Rules & Logic: Expert Systems

Graph Search — The Beginnings

Heuristics & Pathfinding: From Dijkstra to A*

Demo

K-Means Clustering

MinMax (Game Theory)

Pathfinding (Graph Search)

Glossary

Timeline