Chapter 1: Algorithm Complexity Analysis

Vol 2: Algorithm Forest Adventure · Station 1

Your Progress

Welcome to the Algorithm Forest, adventurer. Before you step in, you need a map and a compass. This is the Big O notation — the universal language for measuring "how fast" and "how much memory" your algorithms use.

This chapter will be your guide to the forest. Big O may seem like just a few academic letters at first, but it determines whether your program takes milliseconds or days to run.

No code, just thinking. Because if you can't analyze complexity, you're coding blind.

---

Your Task

Chapter Layers

• Must Read: Big O, Big Ω, Big Θ; time complexity table for common operations; the art of trading space for time
• Recommended: Recursion tree analysis; amortized analysis concept
• Advanced: Master Theorem; rigorous proofs of log-linear complexity

This chapter will NOT teach you

• Rigorous derivations of Master Theorem
• Complex mathematical proofs of amortized analysis

By the end of this chapter, you will be able to:

1. Read any piece of code and determine if it runs in O(1) or O(n²)
2. Explain "trading space for time" with a concrete example
3. Distinguish between average-case and worst-case complexity
4. Recognize the complexity of common data structure operations

---

Encounter: The Village Chief's Abacus

This section introduces how algorithm efficiency is measured — contrasting human intuition (counting on fingers) with formal Big O analysis. Through the concept of problem size n, you'll learn to evaluate algorithms before writing a single line of code.

Common Pitfalls

Complexity Comparison Table

Notation	Meaning	Example
O(1)	Constant	Array random access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Array traversal
O(n log n)	Log-linear	Merge sort, quicksort (average)
O(n²)	Quadratic	Nested loop over array
O(2ⁿ)	Exponential	Recursive Fibonacci (naive)
O(n!)	Factorial	Traveling Salesman (brute force)

(Chinese technical content has been translated to English for clarity.)

---

Pass Challenges

1. What is the Big O of the following code?

for i in range(n):
 for j in range(i, n):
 print(i, j)

2. What is the space complexity of a recursive Fibonacci implementation?

Click for Answers

1. O(n²) — the inner loop runs n-i times, summing to n(n+1)/2 ≈ n²/2
2. O(n) — the recursion stack can go n levels deep

---

Verification Checklist

• [ ] Can visually estimate the complexity of a basic loop
• [ ] Can distinguish O(log n) from O(n) with examples
• [ ] Understands space-time tradeoffs
• [ ] Knows the complexity of basic array/list/hash table operations

---

Common Sticking Points

Issue	Truth
"O(n) means it runs n times"	Not quite — O(n) means the runtime grows linearly with input size
"Big O is everything"	Constant factors and cache behavior matter in practice
"O(2ⁿ) and O(n!) are the same"	No — n! grows much faster than 2ⁿ

---

Traveler's Notes

• Big O matters most on large inputs. A O(n²) algorithm on n=10 is fine; on n=10⁶ it's a disaster.
• Space is a resource too. Don't ignore memory complexity.
• The best optimization is choosing the right data structure. A hash table can turn O(n) lookup into O(1).

---

→ Next Stop Preview

Chapter 2: Arrays and Linked Lists

With Big O in your toolkit, you're ready to compare the two most fundamental data structures. When is continuous memory (arrays) better than fragmented memory (linked lists)? When does cache locality matter more than theoretical complexity?