Mathematical Analysis of Recursive Algorithms
Recursion (Size of Problem: n)
if( Stopping Criteria) then // Base Case
return X // direct solution
else
// General Case: decomposition strategy e.g., n-1, n/2 etc.
return Recursion (decomposition strategy)
Steps in mathematical analysis of recursive algorithms
1. Decide on parameter n indicating input size
2. Identify algorithm’s basic operation
3. Determine worst, average, and best case for input of size n
4. Set up a recurrence relation and initial condition(s)
5. Solve the recurrence to obtain a closed form or estimate the order of magnitude of the
solution
6. Determine Orders of growth of T(n)
Steps to Derive a Recurrence Relation
1. Define the Time Complexity Function
Let T(n) represent the time complexity of a recursive algorithm A, where n is the size of
the input.
2. Identify the Base Case
Determine the base case size, say n = n₀, where the problem is small enough to be solved
directly.
o Time complexity of the base case: T(n₀).
3. Break Down the Problem
Analyze how the problem is divided into smaller subproblems. Suppose it is divided into
k subproblems of sizes m₁, m₂, ..., mₖ.
o Time complexity of subproblems: T(m₁), T(m₂), ..., T(mₖ).
4. Account for Additional Work
Identify the cost of additional work done outside of the recursive calls (e.g., dividing the
problem, merging results).
o Let this cost be c(n) (could be a constant or a function of n).
5. Combine All Components
Now combine the base case, recursive calls, and additional work to form the recurrence
relation:
1
Examples
2
3
ALGORITHM Search(A[l….r], l, r, key)
// A recursive search function.
// Input: An Array A[l..r]
// Output: It returns location of key in given array A, otherwise
-1
{
if (r ≥ l) then
{
m1 = l + (r - l)/3;
m2 = m1 + (r - l)/3;
// If key is present at the m1
if (A[m1] == key) then
return m1;
// If key is present at the m2
if (A[m2] == key) then
return m2;
// If key is present in left one-third
if (A[m1] > key) then
return Search (A, l, m1-1, key);
// If key is present in right one-third
if (A[m2] < key) then
return Search (A, m2+1, r, key);
// If key is present in middle one-third
return Search (A, m2+1, m2-1, key);
}
// We reach here when element is not present in array
return -1;
}
4
Test(n)
{
if(n == 1)
return
else
{
for (i = 1; i < n; i++)
{
Print(i)
}
Test(n/2)
Test(n/2)
}
}
5
Test(n)
{
if(n == 1)
return
else
{
for (i = 1; i < n; i++)
{
Print(i)
}
Test(n/2)
Test(n/2)
}
}
Test(n)
{
if(n == 1)
return
else
{
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ n; j++)
{
Print((i,j))
}
Test(n/2)
Test(n/2)
}
}
Test(n)
{
if(n == 1)
return
else
{
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ n; j++)
{
Print((i,j))
}
Test(n/4)
Test(n/4)
Test(n/4)
}
}
6
How to Solve Recurrence Relation
Recursion Tree Method
It involves:
1. Build the recursion tree(tree of recursive calls) where each node represents a subproblem
of size n/bi. The internal nodes represent recursive calls where the problem is not yet at
the base case and leaf nodes represnts the base cases where no more recursion happens.
2. Calculate the cost at each level. Summing the costs across all levels. The total cost (i.e.,
the time complexity)) then can be computed as
Total Cost = Cost of Internal Nodes + Cost of Leaf Nodes
This is written as:
T(n)= Ic + Lc
Where:
• Ic = Total cost across all internal levels (recursion levels before reaching base case)
• Lc = Total cost at the leaves (base cases)
Step 1: Build the Recursion Tree
• Start with the original recurrence relation, e.g.
T(n) =aT(n/b)+f(n)
7
• Create a tree where:
o The root node is T(n)
o Each node branches into aaa children, each representing a subproblem of size n/b
o This branching continues until the subproblem size reduces to the base case (usually
when size = 1)
Internal Nodes: Recursive calls (still dividing the problem)
Leaf Nodes: Base cases (no further recursion)
Step 2: Calculate the Cost at Each Level
• At each level of the tree, calculate:
o Number of nodes: ai at level i
o Size of each subproblem: n/bi
o Cost per node: f(n/bi)
• Multiply to get total cost at level i:
Costi=ai⋅f(n/bi)
Step 3: Add Costs Across All Levels
Total Cost is:
T(n)=Cost of Internal Nodes (Ic)+Cost of Leaf Nodes (Lc)
T(n) =Ic+Lc
Where:
8
Some Impoertant Formulas
Test(n) Set up a recurrence relation for the given functions.
{ Solve recurrence relation using Recursion Tree
if(n == 1)
Method.
Use appropriate asymptotic notation among O, Ω, and
return
to specify the time efficiency class of the given
else
function.
{
for (i = 1; i < n; i++)
{
Print(i)
}
Test(n/2)
9
Test(n/2)
}
}
Step by step Solution
Continue expanding until the problem size reduces to 1
10
Shortcut Method
11
kllkl
Test(n) Set up a recurrence relation for the given functions. Solve
{ recurrence relation using Recursion Tree Method.
if(n == 1) Use appropriate asymptotic notation among O, Ω, and to
return specify the time efficiency class of the given function.
else
{
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ n; j++)
{
Print((i,j))
}
Test(n/2)
Test(n/2)
}
}
Solution
12
Test(n) Set up a recurrence relation for the given functions. Solve
{ recurrence relation using Recursion Tree Method.
if(n == 1) Use appropriate asymptotic notation among O, Ω, and to
return specify the time efficiency class of the given function.
else
{
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ n; j++)
{
Print((i,j))
}
Test(n/4)
Test(n/4)
Test(n/4)
}
}
Solution
13
Test(n) Set up a recurrence relation for the given functions. Solve
{ recurrence relation using Recursion Tree Method.
if(n == 1) Use appropriate asymptotic notation among O, Ω, and to
return specify the time efficiency class of the given function.
else
{
for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ n; j++)
{
Print((i,j))
}
Test(n/4)
Test(n/2)
}
}
Solution
14
Test(n) Set up a recurrence relation for the given functions.
{ Solve recurrence relation using Recursion Tree
if(n == 1)
Method.
Use appropriate asymptotic notation among O, Ω, and
return
to specify the time efficiency class of the given
else
function.
{
for (i = 1; i < n; i++)
{
Print(i)
}
Test(n/3)
Test(2n/3)
}
}
Solution
15
16
Solve the recurrence relation using the backward substitution (also called iteration) method
Solution
Step-by-Step Solution Using Backward Substitution
Step 1: First Substitution
Start with the given recurrence:
Step 2: Second Substitution
Substitute the recursive term T(n/b):
17
Step 3: Continue Substituting (k times)
Step 4: Stop at Base Case
So now,
18