Algorithms & Data
Structures
Week 2: Algorithm analysis
Professor Alaa E. Abdel-Hakim
Week 2: Asymptotic Analysis Deep-
Dive
• Mastering the Math of Computing
• Moving from Intuition to Proof
Today's Agenda
• 1. Formal Big-O Rules
• 2. Analyzing Loops (Summations)
• 3. Recursion Analysis
• 4. The Fibonacci Disaster: Exponential vs. Polynomial
Step 1: Assign Costs to Primitive Operations
Step 2: Summing the Series (The Math)
Prof. Alaa E. Abdel-Hakim
Step 3: Formulating
𝑇 𝑛
Prof. Alaa E. Abdel-Hakim
Step 4: Deducing Big-O
Prof. Alaa E. Abdel-Hakim
The Sum Rule
• If T1(n) = O(f(n)) and T2(n) = O(g(n))
• Then T1(n) + T2(n) = O(max(f(n), g(n)))
• Example: A loop of N followed by a loop of N^2 is O(N^2).
The Product Rule
• Nested Loops: Inner loop running M times inside outer
loop running N times.
• Result: O(N * M).
Derivation 1: The Square
• Math: n * n = n^2 -> O(n^2)
Derivation 2: The Triangle
• Math: 1+2+3...+(n-1) = n(n-1)/2
• Dominant term: n^2 -> O(n^2)
What about Logarithms?
• Whenever we 'divide the problem in half' each step, we
get O(log n).
• Example: Binary Search, or i *= 2 loops.
Case Study: Factorial Calculation
• Problem: Calculate N! (1 * 2 * 3... * N)
Factorial: Iterative (C++)
• Time: O(n)
• Space: O(1)
Factorial: Recursive (C++)
• Time: O(n)
• Space: O(n) (Due to Call Stack)
The Call Stack Visualization
The Fibonacci Sequence
• 0, 1, 1, 2, 3, 5, 8, 13, 21...
• Definition: F(n) = F(n-1) + F(n-2)
Naive Recursion: Fibonacci
• Let's trace this for n=5...
An Exponential Algorithm For Fibonacci
Numbers
18
The 3 Questions
• Is it correct?
• Precisely Follows the definition
• How much time does it take, as a function of n?
• How many computer stepsT(n)?
• T(n) ≤ 2 for n ≤ 1
• T(n) = T(n - 1) + T(n - 2) + 3 for n > 1
• And can we do better?
•? 19
The Recursion Tree (The 'Mess')
• Each call spawns 2 more calls.
• Height of tree: n
• Total calls: ~2^n
• This is EXPONENTIAL growth.
Activity: Why is Recursive Fib Bad?
• Count the redundant work.
• How many times do we calculate Fib(2) when finding
Fib(5)?
• Answer: 3 times! It gets worse as N grows.
How bad exponential time is?
• T(200) ≥ F200 ≥ 2138
• How long does it take?
• The fastest computer in the world is the NEC Earth Simulator
(clocks 40 trillion steps per second)
• fib1(200) takes 292 seconds ~ 15.7 x 1019 Years!!
22
The Solution: Iterative Fibonacci
• Time: O(n) - Linear!
• Space: O(1)
Comparing Growth Rates
• Polynomial (n^k) vs Exponential (k^n).
• Even n^100 is eventually smaller than 2^n.
O(1) O(log n)
Constant Logarithmic
O(n log n) O(n) O(nc), 0 < c < 1
Quasilinear Linear Fractional Power
O(n2) O(nc), c > 2 O(cn)
Quadratic Polynomial Exponential
The Hierarchy O(nn) = O(n!) 25
of Complexity Factorial
Analyzing 'if-else' statements
• Complexity = max(Complexity of If-block, Complexity of
Else-block).
Analyzing 'While' loops
• Focus on the loop condition. How many times can it be
true?
Space Complexity Deep-Dive
• Recursive depth vs. Auxiliary arrays.
• O(1) vs O(n) vs O(n^2) space.
Summary of Rules
• 1. Constant factors don't matter.
• 2. Low-order terms don't matter.
• 3. Logarithms are your friends.
• 4. Exponentials are your enemies.
Math Review: Log Rules
• log(ab) = log a + log b
• log(n^k) = k log n
• Important for O(n log n) derivations.
Math Review: Geometric Series
• 1 + r + r^2 + ... + r^n = (r^(n+1)-1)/(r-1).
• Critical for analyzing Tree structures.
Code Challenge 1: Find the O
for(int i=1; i<n; i*=2) cout << i;
• Answer: O(log n)
Code Challenge 2: Find the O
• for(int i=0; i<n; i++)
• for(int j=1; j<n; j*=2)
• cout << i+j;
• Answer: O(n log n)
The 'Worst-Case' vs 'Average Case'
• Why we usually focus on the Worst Case (Big-O).
Real World Example: Sorting
• Bubble Sort O(n^2) vs Merge Sort O(n log n).
• At N=1,000,000, one takes days, one takes 1 second.
Questions ??
Prof. Alaa E. Abdel-Hakim