DATA STRUCTURES
& ALGORITHMS
Harvard-Level Comprehensive Study Notes
From First Principles to Advanced Mastery
COMPUTER SCIENCE · ACADEMIC EXCELLENCE SERIES
Complete coverage from arrays to dynamic programming · Real-world examples · Complexity analysis
Section 1 Foundations & Big-O Section 6 Trees & Binary Search Trees
Section 2 Arrays Section 7 Heaps & Priority Queues
Section 3 Linked Lists Section 8 Graphs & Graph Traversal
Section 4 Stacks & Queues Section 9 Sorting Algorithms
Section 5 Hash Tables Section 10 Dynamic Programming
,DATA STRUCTURES & ALGORITHMS Harvard-Level Study Notes
SECTION 1 FOUNDATIONS & BIG-O NOTATION
■ Foundations of Data Structures & Algorithms
◆ 1.1 What Is an Algorithm?
An algorithm is a finite, ordered sequence of well-defined instructions that transforms one or more inputs into
one or more outputs. Think of it like a recipe: it takes raw ingredients (inputs), follows step-by-step instructions
(the algorithm), and produces a finished dish (output).
■ Real-World Analogy: Pizza Delivery Algorithm
Input: Customer order, kitchen inventory, driver availability
Steps: Receive order → Prepare pizza → Quality check → Assign driver → Navigate → Deliver
Output: Pizza delivered within estimated time
A bad algorithm (driver takes wrong turns every time) wastes resources. A good algorithm is fast, correct, and
efficient.
An algorithm must satisfy five essential properties:
• Finiteness: Must terminate after a finite number of steps
• Definiteness: Each step must be precisely and unambiguously defined
• Input: Zero or more inputs are accepted
• Output: One or more outputs are produced
• Effectiveness: Each step must be basic enough to be carried out in finite time
◆ 1.2 What Is a Data Structure?
A data structure is a way of organizing, managing, and storing data so it can be accessed and modified
efficiently. The choice of data structure directly impacts algorithm performance.
■ Real-World Analogy: Library Organization
No structure: Books scattered on floor → Finding a book: O(n) — must check every book
Array (shelves by number): Books on numbered shelves → Finding by position: O(1)
Hash Table (catalog system): Books indexed by title → Finding by name: O(1) average
Tree (Dewey Decimal): Books organized hierarchically → Searching by subject: O(log n)
The right data structure transforms an impossible task into a trivial one.
Computer Science · Academic Excellence Series Page 2
, DATA STRUCTURES & ALGORITHMS Harvard-Level Study Notes
◆ 1.3 Big-O Notation — Analyzing Efficiency
Big-O notation describes the upper bound of an algorithm's time or space complexity as input size n grows
toward infinity. It answers: "As data gets bigger, how much slower does my algorithm get?"
Why do we need it? Two algorithms may sort 1,000 items in the same time. But Algorithm A takes n² steps
and Algorithm B takes n·log(n) steps. When n = 1,000,000:
• Algorithm A: 1,000,000,000,000 operations — takes days
• Algorithm B: 20,000,000 operations — takes seconds
■ The Complexity Hierarchy (best to worst)
Notation Name n=100 ops Real Example
O(1) Constant 1 Array index access, hash lookup
O(log n) Logarithmic 7 Binary search, balanced BST lookup
O(n) Linear 100 Linear search, single loop
O(n log n) Log-linear 700 Merge sort, heap sort
O(n2) Quadratic 10,000 Bubble sort, nested loops
O(n3) Cubic 1,000,000 Naive matrix multiplication
O(2n) Exponential ~1030 Recursive Fibonacci, subsets
O(n!) Factorial ~10158 Brute-force TSP, permutations
■ Rules for Computing Big-O
• Drop constants: O(3n) → O(n); O(500) → O(1)
• Drop lower-order terms: O(n² + n + 1) → O(n²)
• Sequential steps add: O(n) + O(m) → O(n + m)
• Nested loops multiply: A loop of n inside a loop of n → O(n²)
• Different variables stay separate: O(n·m) cannot be simplified unless n ≈ m
■ Key Insight: Best, Average, Worst Case
Best case (Ω — Omega): The minimum operations needed
Average case (Θ — Theta): Expected performance on typical input
Worst case (O — Big-O): Maximum operations needed — this is what we optimize for
Example: Linear search: Ω(1) target is first | Θ(n/2) target in middle | O(n) target is last
◆ 1.4 Space Complexity
Computer Science · Academic Excellence Series Page 3
& ALGORITHMS
Harvard-Level Comprehensive Study Notes
From First Principles to Advanced Mastery
COMPUTER SCIENCE · ACADEMIC EXCELLENCE SERIES
Complete coverage from arrays to dynamic programming · Real-world examples · Complexity analysis
Section 1 Foundations & Big-O Section 6 Trees & Binary Search Trees
Section 2 Arrays Section 7 Heaps & Priority Queues
Section 3 Linked Lists Section 8 Graphs & Graph Traversal
Section 4 Stacks & Queues Section 9 Sorting Algorithms
Section 5 Hash Tables Section 10 Dynamic Programming
,DATA STRUCTURES & ALGORITHMS Harvard-Level Study Notes
SECTION 1 FOUNDATIONS & BIG-O NOTATION
■ Foundations of Data Structures & Algorithms
◆ 1.1 What Is an Algorithm?
An algorithm is a finite, ordered sequence of well-defined instructions that transforms one or more inputs into
one or more outputs. Think of it like a recipe: it takes raw ingredients (inputs), follows step-by-step instructions
(the algorithm), and produces a finished dish (output).
■ Real-World Analogy: Pizza Delivery Algorithm
Input: Customer order, kitchen inventory, driver availability
Steps: Receive order → Prepare pizza → Quality check → Assign driver → Navigate → Deliver
Output: Pizza delivered within estimated time
A bad algorithm (driver takes wrong turns every time) wastes resources. A good algorithm is fast, correct, and
efficient.
An algorithm must satisfy five essential properties:
• Finiteness: Must terminate after a finite number of steps
• Definiteness: Each step must be precisely and unambiguously defined
• Input: Zero or more inputs are accepted
• Output: One or more outputs are produced
• Effectiveness: Each step must be basic enough to be carried out in finite time
◆ 1.2 What Is a Data Structure?
A data structure is a way of organizing, managing, and storing data so it can be accessed and modified
efficiently. The choice of data structure directly impacts algorithm performance.
■ Real-World Analogy: Library Organization
No structure: Books scattered on floor → Finding a book: O(n) — must check every book
Array (shelves by number): Books on numbered shelves → Finding by position: O(1)
Hash Table (catalog system): Books indexed by title → Finding by name: O(1) average
Tree (Dewey Decimal): Books organized hierarchically → Searching by subject: O(log n)
The right data structure transforms an impossible task into a trivial one.
Computer Science · Academic Excellence Series Page 2
, DATA STRUCTURES & ALGORITHMS Harvard-Level Study Notes
◆ 1.3 Big-O Notation — Analyzing Efficiency
Big-O notation describes the upper bound of an algorithm's time or space complexity as input size n grows
toward infinity. It answers: "As data gets bigger, how much slower does my algorithm get?"
Why do we need it? Two algorithms may sort 1,000 items in the same time. But Algorithm A takes n² steps
and Algorithm B takes n·log(n) steps. When n = 1,000,000:
• Algorithm A: 1,000,000,000,000 operations — takes days
• Algorithm B: 20,000,000 operations — takes seconds
■ The Complexity Hierarchy (best to worst)
Notation Name n=100 ops Real Example
O(1) Constant 1 Array index access, hash lookup
O(log n) Logarithmic 7 Binary search, balanced BST lookup
O(n) Linear 100 Linear search, single loop
O(n log n) Log-linear 700 Merge sort, heap sort
O(n2) Quadratic 10,000 Bubble sort, nested loops
O(n3) Cubic 1,000,000 Naive matrix multiplication
O(2n) Exponential ~1030 Recursive Fibonacci, subsets
O(n!) Factorial ~10158 Brute-force TSP, permutations
■ Rules for Computing Big-O
• Drop constants: O(3n) → O(n); O(500) → O(1)
• Drop lower-order terms: O(n² + n + 1) → O(n²)
• Sequential steps add: O(n) + O(m) → O(n + m)
• Nested loops multiply: A loop of n inside a loop of n → O(n²)
• Different variables stay separate: O(n·m) cannot be simplified unless n ≈ m
■ Key Insight: Best, Average, Worst Case
Best case (Ω — Omega): The minimum operations needed
Average case (Θ — Theta): Expected performance on typical input
Worst case (O — Big-O): Maximum operations needed — this is what we optimize for
Example: Linear search: Ω(1) target is first | Θ(n/2) target in middle | O(n) target is last
◆ 1.4 Space Complexity
Computer Science · Academic Excellence Series Page 3
