Algorithms and Data Structures 1

CS 0445

Fall 2024

Analysis of Recursive Algorithms

Sherif Khattab
ksm73@[Link]
(Slides are adapted from Textbook and Dr. Ramirez’s CS 0445 slides.)
 Runtime analysis of Recursive Algorithms
• Step 0: Assume running time of recursive algorithm is a function T(n) of
input size n
• Step 1: Build a Recurrence Relation for the running time function T(n)
• Don’t forget the base case (e.g., T(1))
• Step 2: Build an intuition to make a guess for a closed form for T(n)
• By evaluating T(n) for small values of n
• Step 3: Try to prove your guess for T(n) using proof by induction
• If not successful, go back to Step 2

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 2

 Example 1: countDown
• Assume running time of countDown is a function of n: T(n)
• T(n) = 1 + 1 + ??
• What is the running time of countdown(n-1)?
• Can we use the function T(n)?
• Yes! The running time of countdown(n-1) is T(n-1)
• T(n) = 2 + T(n-1)
• = T(n-1) + O(1)
• T(1) = O(1)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 3

 Running Time Analysis of Recursive Algorithms
• T(1) = 1 … (1)
• T(n) = T(n-1) + 1 for n>1 … (2)
• The above equation is called a Recurrence Relation
• T(2) = T(1) + 1 = 2
• T(3) = T(2) + 1 = 2 + 1 = 3
• T(4) = T(3) + 1 = 3 + 1 = 4
• …
• We have an intuition that the running time is linear
• T(n) = n … (3)
• Let’s prove (3) by induction
• Base Case:
• From (1): T(1) = 1
• From (3): T(1) = 1
• (3) applies to the base case
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 4
 Running Time Analysis of Recursive Algorithms
• Inductive Step:
• Assume that (3) is true for all values < k and prove that it is true for k
• Inductive hypothesis: T(n) = n for all n<k … (4)
• We want to prove that T(k) = k
• From (2), T(k) = T(k-1) + 1 T(1) = 1 … (1)
• From (4), T(k) = (k-1) + 1 = k
T(n) = T(n-1) + 1 for n>1 … (2)
• End of Proof that T(n) = n
• So, running time of countdown is O(n)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 5

 Example 2: powerRecursive
• Assume the running time of powerRecursive is a function of exponent y:
T(y)
• T(y) = O(1) + running time of power(x, y/2)
• What is the running time of power(x, y/2)?
• Can we use the function T(y)?
• Yes! The running time of power(x, y/2) is T(y/2)
• T(y) = T(y/2) + O(1)
• Base Case: T(1) = O(1)

1
x

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 6

 Recurrence Relation for powerRecursive
• We have a recurrence relation!
• T(1) = 1 … (1)
• T(y) = T(y/2) + 1 for y>1 … (2)
• The above equations called Recurrence Relation
• Guess a closed form for T(y)
• T(2) = T(1) + 1 = 2
• T(4) = T(2) + 1 = 2 + 1 = 3
• T(8) = T(4) + 1 = 3 + 1 = 4
• T(16) = T(8) + 1 = 4 + 1 = 5
• When y doubles  T(y) increases by 1
• Intuition: T(y) is logarithmic in y
• T(y) = log(y) + 1 … (3)
• Let’s prove (3) by induction
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 7
 Proof by Induction for T(y) of powerRecursive
P(y): T(y) = log(y) + 1 for y>=1 … (3)
• Base Case: Prove P(1): T(1) = log(1) + 1
• From (1) in Recurrence Relation: LHS = T(1) = 1
• RHS = log(1) + 1 = 0 + 1 = LHS T(1) = 1 … (1)
• Induction Hypothesis: (I.H.) T(y) = T(y/2) + 1 for y>1 … (2)
• Assume P(y) holds for all y < k
• T(y) = log(y) + 1 for all y < k
• Induction Step: Prove P(k): T(k) = log(k) + 1
• LHS = T(k) = T(k/2) + 1 … from (2) in Recurrence Relation
• = log(k/2) + 1 + 1 … from I.H.
• = log(k/2) + 2
• = log(k/2) + log 4
• = log((k/2)*4) = log(2k)
• = log k + log 2
• = log k + 1 = RHS
• So, the running time
CS of powerRecursive
0445 is log(y)
– Algorithms & Data Structures + 1Khattab
1 – Sherif = O(log y) 8
 Example 3: Towers of Hanoi Problem
• Recursive algorithm to solve any number of disks.

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 9

 Recurrence Relation for Towers of Hanoi
• Assume running time of solveTowers is a function T(n) of input size n
• What is n in this problem?
• number of disks to move
• T(1) = 1
• T(n) = 2*running time of solveTowers(numberOfDisks – 1) + 1
• = 2*T(n-1) + 1

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 10

 Recurrence Relation for Towers of Hanoi
• Step 1: Recurrence Relation for the running time function T(n)
• T(1) = 1
• T(n) = 2T(n-1) + 1 for n > 1
• Step 2: Guess a closed form for T(n)
• By evaluating T(n) for small values of n
• T(2) = 2T(1) + 1 = 3
• T(3) = 2T(2) + 1 = 7
• T(4) = 2T(3) + 1 = 15
• T(5) = 2T(4) + 1 = 31
• …
• not linear
• increase n by 1  almost doubling of T(n)
• exponential function
• T(n) = 2n
• would that work?
• Nope, why?
• T(n) = 2n - 1 CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 11
 Proof by Induction for T(n) of Towers of Hanoi
P(n): T(n) = 2n – 1 for n >= 1
• Base Case: Prove P(1): T(1) = 21-1
• LHS = T(1) = 1 … from (1)
• RHS = 21 – 1 = 2 – 1 = 1 = LHS T(1) = 1 … (1)
• Induction Hypothesis (I.H.): T(n) = 2T(n-1) + 1 for n>1 … (2)
• Assume P(n) holds for all values n < k
• T(n) = 2n – 1 for n < k
• Induction Step: Prove P(k): T(k) = 2k - 1
• LHS = T(k) = 2 T(k-1) + 1 … from (2)
• = 2 (2k-1 - 1) + 1 from I.H.
• = 2k – 2 + 1 = 2k – 1 = RHS
• So, the running time of solveTowers is 2n – 1 = O(2n)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 12

Example 4: Binary Search

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 13

 Recurrence Relation for Binary Search
• Assume running time of binarySearch is a function T(n) of input size n
• T(1) = 1
• T(n) = O(1) + 1*running time of binarySearch on half the array
• = T(n/2) + 1

>=

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 14

 Recurrence Relation for Binary Search
• Step 1: Recurrence Relation for the running time function T(n)
• T(1) = 1
• T(n) = T(n/2) + 1 for n > 1
• Step 2: Guess a closed form for T(n)
• By evaluating T(n) for small values of n
• T(2) = T(1) + 1 = 2
• T(4) = T(2) + 1 = 3
• T(8) = T(4) + 1 = 4
• T(16) = T(8) + 1 = 5
• …
• not linear
• n doubles T(n) increases by 1
• logarithmic function
• T(n) = log n
• would that work?
• Nope, why?
• T(n) = log n + 1 CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 15
 Proof by Induction for T(n) of Binary Search
P(n): T(n) = log n + 1 for n >= 1
• Base Case: Prove P(1): T(1) = log 1 + 1
• LHS = T(1) = 1 … from (1)
• RHS = log 1 + 1 = 0 + 1 = 1 = LHS T(1) = 1 … (1)
• Induction Hypothesis (I.H.): T(n) = T(n/2) + 1 for n>1 … (2)
• Assume P(n) holds for all values n < k
• T(n) = log n + 1 for n < k
• Induction Step: Prove P(k): T(k) = log k + 1
• LHS = T(k) = T(k/2) + 1 … from (2)
• = log (k/2) + 1 + 1 from I.H.
• = log (k/2) + log 4 = log 2k = log k + 1 = RHS
• So, the running time of binarySearch is log n + 1 = O(log n)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 16

 Recursion Tree Analysis
• Used recursion tree to trace recursion algorithms
• Each node represents one recursive call
• Terminal nodes are called leaves
• Use recursion tree to estimate the running time of a recursive algorithm

running time = number of nodes * time per node

Recursion tree for Fib(6)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 17
 Example 1: Fibonacci numbers

• number of nodes almost doubles as we go

down level by level
• 1st level: 1 node
• 2nd level: 2 nodes
• 3rd level: 4 nodes
• …
• number of nodes <= 1 + 2 + 4 + 8 + 16 + ...
• How many levels?
• number of levels = n
• e.g., the recursion tree for F6 has 6 levels
• number of nodes <= 1 + 2 + 4 + 8 + … + 2 n-1
• <= (a(rn - 1))/(r - 1)
• = (1(2n-1))/(2-1) = 2n-1
• = O(2n)
• Running time per node is O(1) (why?)
• Total running time = O(2n) * O(1) = O(2n) 18
 Isn’t that too slow?
Yes! Recursion may lead a poor solution, worse than iterative

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 19

 Example 2: Towers of Hanoi

• Let’s draw the recursion tree for solveTowers on 6 disks

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 20

 Recursion Tree for Towers of Hanoi
• number of nodes doubles as we go down level by level
• 1st level: 1 node
• 2nd level: 2 nodes
• 3rd level: 4 nodes
• …
• number of nodes = 1 + 2 + 4 + 8 + 16 + ...
• How many levels?
• number of levels = n
• e.g., the recursion tree for solveTowers on 6 disks has 6 levels
• number of nodes = 1 + 2 + 4 + 8 + … + 2n-1
• <= (a(rn - 1))/(r - 1)
• = (1(2n-1))/(2-1) = 2n-1
• = O(2n)
• Running time per node is O(1) (why?)
• Total running time = O(2n) * O(1) = O(2n)
• Exponential! CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 21
 Example 3: Binary Search
• To simplify analysis, we'll cheat a bit:
1) Assume that the array is cut exactly in half with each iteration
• In reality, it may vary by one element either way
2) Assume that the initial size of the array, n, is an exact power of 2, or 2 k for some
k
• In reality, it can be any value
• However, it will not affect our results
• Ok, so we have the following:
• At call 0: n0 = 2k
• At call 1, n1 = n0/2 (in terms of k?)
• = 2k-1
• At call 2, n2 = n1/2 (in terms of k?)
• = 2k-2
• At call i, ni = ni-1/2 (in terms of k?)
• = 2k-i
• Last call is when n = 1
• = 20 CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab
22
 Time complexity of Binary Search
• Observation: In call number i, subarray size = 2k-i
• How many calls are needed?
• In the last call, k-i = 0  i = k
• From call number 0 to call number k?
• k+1 calls  k+1 tree nodes
• We do one key comparison per call  O(1) time per tree node
• Thus, we have a total of (k+1)*1 comparisons maximum
• But, n = 2k
• So, k = ?
• k = log2n
• which makes k + 1 = ?
• = log2n + 1
• This leads to our final answer of ?
• O(log2n)

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

23
 Binary Search on a Sorted Chain
• Observation: To find the middle of the chain, traverse the whole chain
• Time per call = O(length of sub-chain)
• Same number of calls as Binary Search on Sorted Array
• Total time = n + n/2 + n/4 + … + 1
• = n(1 + ½ + ¼ + … + 1/n)
• < n(1 + ½ + ¼ + … + 1/n + …)
• = n[(1/(1- ½)]
• = n[1/½] = 2n = O(n)
• Same asymptotic runtime as sequential search!

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 24

 Note on input size
• Our goal is to model running time in terms of input size
• The input size is number of bits needed to represent the input
• For the power function, exponent y is represented using how many bits?
• log y bits
• So, the input size is not y, the exponent value, but …
• The input size is log y
• So, the recursive power function has O(log y) runtime
• This is linear in log y, the input size
• So, powerRecursive has linear running time

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 25

 What is recursion good for?
• For some problems, a recursive approach is
more natural and simpler to understand than an
iterative approach
• traversing a linked list backwards
• reversing a linked list

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

26
 What is recursion good for?
• For other problems, it is very difficult to even
conceive an iterative approach, especially if
multiple recursive calls are required in the
recursive solution
• Towers of Hanoi
• Eight Queens

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

27
 What is recursion good for?
• For other problems, a recursive approach
allows for a more efficient solution than an
iterative approach
• e.g., exponentiation xy
• General approach is called Divide and Conquer
• more examples next week

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

28
 Divide and Conquer
• A problem can be solved by breaking it down to
"smaller" problems in a systematic way
• subproblems(s) are identical in nature to the original
• This is why these problems can be solved quite nicely using
recursion
• subproblem(s) are a fraction of the size of the original

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

29
 Divide and Conquer

• We can think of each lower level as solving

the same problem as the level above
4 The only difference in each level is the size of the
problem, which is ½ of that of the level above it
for example
4 Note how quickly the problem size is reduced

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

30
 When to use recursion?
• recursion is more natural and simpler for
many problems
• extremely difficult to even conceive an
iterative approach
• recursion allows for a more efficient solution

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

31
 Limitations of Recursion
• Recursion Overhead is high
• Recursion may lead a less efficient solution than an iterative approach

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 32

 Overhead of Recursion
• Recursive calls have overhead
• Space: each activation record (AR) takes up memory in the
run-time stack (RTS)
• If too many calls "stack up,” memory can be a problem
• Time: generating ARs and manipulating the RTS takes time
• A recursive algorithm will always run more slowly than an equivalent
iterative version
• Once a recursive algorithm is developed, in some cases
we can convert it into a faster iterative version

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

33
 Tail Recursion
• When recursive call is the last statement of the method
• No further processing after the return of the recursive call
• Some algorithms we have seen so far are tail recursive
and some are not

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

34
 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 35

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 36

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 37

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 38

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 39

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 40

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 41

 Tail-recursive?

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 42

 Implications of Tail Recursion
• Any tail recursive algorithm can be converted into an
iterative algorithm in a systematic way
• some compilers do that automatically

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab

43
 Converting Tail Recursion into Iteration
• Step 1: make the recursive call inside an if statement
• Step 2: change the if statement to a while loop
• Step 3: replace the recursive call by a set of assignment
statements in the form
• parameter = argument

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 44

 Example
Step 1: Put the recursive call inside an if statement
Public static void countdown(int integer){
if(integer == 1)
[Link](integer);
else
countdown(integer-1);
}

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 45

 Example
Step 2: Convert if to while

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 46

 Example
Step 3: replace recursive call by assignment statement(s)
• parameter = argument
• integer = integer -1

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 47

Example 2: Towers of Hanoi

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 48

 Converting Recursion to Iteration using an Explicit Stack
• We can convert recursion into iteration by replacing the Runtime Stack
with an explicit Stack
• Basic idea: replace recursive call by push to stack
• Example: Lab 5

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 49

Final Note on Runtime Analysis of Recursive Algorithms
• In general, we can either use proof by induction or
recursion tree in most of the cases
• Please check more examples on Canvas

CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 50