🏢

Big O Notation
Shopping Mall Story

You walk into a 5-floor mall with 1,000 shops.
You want to buy a mobile phone.
Every path you take teaches you a different Big O complexity.

7 Complexities
1 Mall Analogy
Student Friendly
Real Visuals
1
Chapter 1  ·  Constant Time
O(1) — Instant
⚡ Speed: Instant  |  🚀 Always 1 step

You walk into the mall and head straight to the Reception Desk.

You: "Where is the Samsung Store?"
Receptionist: "3rd Floor, Shop No. 327."

You go directly there. No searching. No walking around.

It does not matter if the mall has 100 shops, 1,000 shops, or 10,000 shops — the receptionist gives the answer in exactly 1 step.

✅
Time never changes. Whether you look up 1 item or 1 billion items in a HashMap, it always takes exactly 1 step.
🚀 Big O = O(1)
Direct Access — Always 1 Step
🎪 Reception
Ask once
→
✅ Shop 327
3rd Floor
Same 1 step for ANY mall size:
100 shops
1,000 shops
10,000 shops
⚡ Always just 1 step
n = 10
1
step
n = 1,000
1
step
n = 1,000,000
1
step
Real examples: HashMap.get(), array[5], Stack.pop()
2
Chapter 2  ·  Logarithmic Time
O(log n) — Fast
🏎️ Speed: Fast  |  Cuts the problem in HALF every step

The receptionist is busy. You use the Digital Mall Directory touchscreen.

Instead of checking every single shop, it asks smart questions that eliminate half the possibilities each time:

Is it on Floor 3 or above? → No
Is it in the Electronics zone? → Yes
Is it in the North wing? → Yes
Is it Samsung? → Found!

Each question cuts the remaining shops in half. Like Google Maps narrowing down a location.

✅
1,000 shops → only 10 questions.
1 billion items → only 30 questions. The bigger the data, the bigger the advantage!
🏎️ Big O = O(log n)
Each step cuts the search in HALF
1,000 shops — Start here
↓ Half removed (wrong floor)
500 shops remain
↓ Half removed (wrong zone)
250 shops remain
↓ Half removed (wrong wing)
125 shops remain
↓ Half removed (wrong category)
62 shops remain
↓ ... only a few more questions ...
✅ Samsung Found! (~10 questions total)
Real examples: Binary Search, BST lookup, phone book search
3
Chapter 3  ·  Linear Time
O(n) — Linear
🚙 Speed: Linear  |  One check per shop

No receptionist. No directory. You must walk shop by shop.

Shop 1 — Clothing ❌
Shop 2 — Shoes ❌
Shop 3 — Food ❌
... keep walking ...
Shop 742 — Samsung ✅ Found!

In the worst case, the Samsung store is the very last shop you check.

If the mall doubles in size from 500 to 1,000 shops, your walking time doubles too. The work grows directly with the input.

✅
Fair and predictable. 100 shops = 100 checks. 1,000 shops = 1,000 checks. Like a teacher calling attendance one by one.
🚙 Big O = O(n)
Checking shops one by one (20 shown)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
✅
16
17
18
19
20
❌ = checked & skipped   ✅ = Found at shop 15
n = 100 shops
100
max checks
n = 1,000 shops
1,000
max checks
Real examples: Linear search, printing all items, counting
4
Chapter 4  ·  Linearithmic Time
O(n log n) — Okay
🚗 Speed: Okay  |  The best possible sorting speed

You are now the Mall Manager. A delivery of 10,000 products arrives. You need to arrange them for opening day.

Instead of comparing every product with every other product (that would be O(n²)!), you use a smarter strategy:

Step 1: Split products into categories
  → Electronics, Fashion, Food, Books
Step 2: Sort each category separately
  → Each section sorted quickly
Step 3: Merge them into one organised mall
✅
The best any sorting algorithm can achieve. This is exactly how Merge Sort, Quick Sort, and Python's sorted() work under the hood.
🚗 Big O = O(n log n)
Split → Sort each → Merge
📦 10,000 Products (unsorted)
↓ Split into 4 groups
📱 Electronics
👗 Fashion
🍕 Food
📚 Books
↓ Sort each group
📱 Sorted ✓
👗 Sorted ✓
🍕 Sorted ✓
📚 Sorted ✓
↓ Merge all groups
📚 Books
📱 Electronics
👗 Fashion
🍕 Food
... all 10,000 sorted ✅
Real examples: Merge Sort, Heap Sort, Arrays.sort(), Python sorted()
5
Chapter 5  ·  Quadratic Time
O(n²) — Very Slow
🐢 Speed: Slow  |  Every item checks every other item

You want the best price for your mobile. So you visit every mobile shop — and for each shop, you compare its price with every other shop.

Samsung ↔ Apple
Samsung ↔ Vivo
Samsung ↔ Oppo
Apple ↔ Vivo
Apple ↔ Oppo
Vivo ↔ Oppo
... and so on for ALL shops

This is exactly how Bubble Sort works — two nested loops comparing every pair.

⚠️
Double the shops → 4× the work!
100 shops = 10,000 comparisons. 1,000 shops = 1,000,000 comparisons. Avoid for large data.
🐢 Big O = O(n²)
Every shop vs every other shop
Samsung Apple Vivo Oppo
Samsung — ✓ Compare ✓ Compare ✓ Compare
Apple ✓ Compare — ✓ Compare ✓ Compare
Vivo ✓ Compare ✓ Compare — ✓ Compare
Oppo ✓ Compare ✓ Compare ✓ Compare —
4 shops = 12 comparisons shown above
n = 10 shops
100
comparisons
n = 100 shops
10K
comparisons
n = 1,000 shops
1M
comparisons
Real examples: Bubble Sort, Selection Sort, finding all pairs
6
Chapter 6  ·  Exponential Time
O(2ⁿ) — Explosive
💥 Speed: Explosive  |  Doubles with every new item

Every shop you visit gives you exactly 2 choices: Buy or Skip. You want to try every possible combination of decisions.

3 shops → 8 possible combinations:
Buy-Buy-Buy, Buy-Buy-Skip,
Buy-Skip-Buy, Buy-Skip-Skip,
Skip-Buy-Buy, Skip-Buy-Skip,
Skip-Skip-Buy, Skip-Skip-Skip

Each new shop doubles the total number of combinations.

Like a WhatsApp forward: you send to 2 friends, each sends to 2 more... after 30 forwards, over 1 BILLION messages!

🚨
20 shops → 1,048,576 combinations.
30 shops → over 1 billion. Only practical when n is very small (n ≤ 20).
💥 Big O = O(2ⁿ)
Buy or Skip — combinations explode!
🏪 Shop 1
↙ Buy            Skip ↘
Buy Shop1
Skip Shop1
↙↘              ↙↘
B+Buy2
B+Skip2
S+Buy2
S+Skip2
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
BBB
BBS
BSB
BSS
SBB
SBS
SSB
SSS
3 shops = 2³ = 8 combinations
n = 10
1,024
combinations
n = 20
~1M
combinations
n = 30
~1B
combinations
Real examples: Naive Fibonacci, finding all subsets
7
Chapter 7  ·  Factorial Time
O(n!) — Impossible
☠️ Speed: Impossible  |  Every possible ordering

You decide: "I will visit every shop in every possible order."

With just 4 shops — Samsung, Apple, Vivo, Oppo — the possible visit orders are:

Samsung → Apple → Vivo → Oppo
Samsung → Vivo → Apple → Oppo
Apple → Samsung → Oppo → Vivo
... 24 different routes for just 4 shops!

That is 4! = 4 × 3 × 2 × 1 = 24.

With 10 shops: 10! = 3,628,800 routes.
With 20 shops: a computer checking 1 billion routes per second would take 77 YEARS.

☠️
Only ever used for n ≤ 10. This is why the Travelling Salesman Problem (finding the shortest route visiting all cities) uses smart shortcuts instead of brute force.
☠️ Big O = O(n!)
All 24 routes for 4 shops (S=Samsung, A=Apple, V=Vivo, O=Oppo)
S→A→V→O
S→A→O→V
S→V→A→O
S→V→O→A
S→O→A→V
S→O→V→A
A→S→V→O
A→S→O→V
A→V→S→O
A→V→O→S
A→O→S→V
A→O→V→S
V→S→A→O
V→S→O→A
V→A→S→O
V→A→O→S
V→O→S→A
V→O→A→S
O→S→A→V
O→S→V→A
O→A→S→V
O→A→V→S
O→V→S→A
O→V→A→S
4 shops = 4! = 24 routes
n = 5 shops
120
routes
n = 10 shops
3.6M
routes
n = 20 shops
77 yrs
to check all
Real examples: Travelling Salesman brute-force, all permutations

Complete Story Flow

Every path through the mall — one for each complexity

🏢 Shopping Mall — Need a Mobile Phone 5 Floors · 1,000 Shops · 7 Different Paths
⚡
Ask the receptionist for the exact shop number
One question → direct answer → Shop 327. Zero searching.
O(1)
│
🏎️
Use the digital directory — halve the options each time
1000 → 500 → 250 → 125 → Found. Only ~10 questions for 1,000 shops.
O(log n)
│
🚙
Walk shop by shop — no map, no help
Check Shop 1, Shop 2, Shop 3... worst case: 1,000 checks for 1,000 shops.
O(n)
│
🚗
Mall manager sorts 10,000 products — split, sort, merge
Divide into categories → sort each → combine. Much faster than O(n²) sorting.
O(n log n)
│
🐢
Compare every shop price with every other shop
Samsung vs Apple, Samsung vs Vivo... 100 shops = 10,000 comparisons!
O(n²)
│
💥
Try every Buy / Don't Buy combination for each shop
Each new shop doubles all combinations. 30 shops = over 1 billion choices!
O(2ⁿ)
│
☠️
Visit every shop in every possible order
10 shops = 3,628,800 routes. 20 shops = a computer needs 77 YEARS.
O(n!)
Quick Reference — n = 100 shops
O(1)
1 step
O(log n)
7 steps
O(n)
100 steps
O(n log n)
664 steps
O(n²)
10,000 steps
O(2ⁿ)
1.27×10³⁰ ♾️
O(n!)
9.3×10¹⁵⁷ ☠️