Analysis of Recursive Algorithms

Analysis Of Recursive Selection Sort

private static void selectionSort(int[] x, int n)
{
int minPos;
if (n > 0)
{
minPos = findMinPos(x, n);
swap(x, minPos, n);
selectionSort(x, n - 1);
}
}
private static int findMinPos (int[] x, int n)
{
int k = n;
for(int i = 0; i < n; i++)
if(x[i] < x[k]) k = i;
return k;
}
private static void swap(int[] x, int minPos, int n)
{
int temp=x[n]; x[n]=x[minPos]; x[minPos]=temp;
}
findMinPos is O(n), and swap is O(1), therefore the recurrence relation for the
running time of the selectionSort method is:
T(0) = a (1)
T(n) = T(n – 1) + n + c if n > 0 (2)
= [T(n-2) +(n-1) + c] + n + c = T(n-2) + (n-1) + n + 2c by substituting T(n-1) in (2)
= [T(n-3) + (n-2) + c] +(n-1) + n + 2c= T(n-3) + (n-2) + (n-1) + n + 3c by substituting T(n-2)
= T(n-4) + (n-3) + (n-2) + (n-1) + n + 4c
= …… = T(n-k) + (n-k + 1) + (n-k + 2) + …….+ n + kc
The base case is reached when n – k = 0 → k = n, we then have :
T(n)= T(0)+1+2+3+ +(n-2)+(n-1)+ n +nc =a+ 1+2+3+ +(n-2) + (n-1)+ n +nc= a+nc+∑𝑛𝑖=1 𝑖
𝑛(𝑛+1) 𝑛2 1
=a+nc+ = + (𝑐 + ) 𝑛 + 𝑎
2 2 2

Therefore, Recursive Selection Sort is O(n2)

Analysis Of Recursive Towers of Hanoi Algorithm
Problem Statement
Move all the disks stacked on the first tower over to the last tower using a helper tower in the
middle. While moving the disks, certain rules must be followed. These are :
1. Only one disk can be moved.
2. A larger disk can not be placed on a smaller disk.
Tower of Hanoi Default Setup

We solve this question using simple recursion. To get the three disks over to the final tower you
need to :
Take the disk number 1 and 2 to tower B.
Move disk number 3 to tower C.
Take disk number 1 and 2 from B to C.
Of course, you can’t do it like this because of the constraints. However, we can use this to create
a function that does it recursively.
public static void hanoi(int n, char from, char to, char temp)
{
if (n == 1)
System.out.println(from + " --------> " + to);
else
{
hanoi(n - 1, from, temp, to);
System.out.println(from + " --------> " + to);
hanoi(n - 1, temp, to, from);
}
}
The recurrence relation for the running time of the method hanoi is:
T(n) = a if n = 1
T(n) = 2T(n - 1) + b if n > 1
Expandions:
T(n) = 2[2T(n – 2) + b] + b = 22 T(n – 2) + 3b by substituting T(n – 1)
= 22 [2T(n – 3) + b] + 3b = 23 T(n – 3) + 7b by substituting T(n-2)
= 23 [2T(n – 4) + b] + 7b = 24 T(n – 4) + 15b by substituting T(n – 3)
=2k T(n – k) + (2k -1)b
The base case is reached when n – k = 1 → k = n – 1, we then have:
T(n)= (2n-1)a+(2n-1-1)b=(2n-1)(a+b)-b
Therefore, The method hanoi is O(2n)
Master Theorem (Master Method)
The master method provides an estimate of the growth rate of the solution for recurrences of the
form:

where a ≥ 1, b > 1 and the overhead function f(n) > 0

If T(n) is interpreted as the number of steps needed to execute an algorithm for an input of size
n, this recurrence corresponds to a “divide and conquer” algorithm, in which a problem of size
n is divided into a sub-problems of size n / b, where a, b are positive constants T(n) = aT(n/b)
+ f(n)
Divide-and-conquer algorithm:
• divide the problem into a number of subproblems
• conquer the subproblems (solve them)
• combine the subproblem solutions to get the solution to the original problem
Example: Merge Sort
• divide the n-element sequence to be sorted into two n/2- element sequences.
• conquer the subproblems recursively using merge sort.
• combine the resulting two sorted n/2-element sequences by merging
The Simplified Master Method for Solving Recurrences:
• Consider recurrences of the form:
T(1) = 1
T(n) = aT(n/b) + knc
for constants a ≥ 1, b > 1, c  0, k ≥ 1 then:
1. 𝑇(𝑛) ∈ 𝑂(𝑛log b𝑎 ) if a > bc
2. 𝑇(𝑛) ∈ 𝑂(𝑛c log 𝑛) if a = bc
3. 𝑇(𝑛) ∈ 𝑂(𝑛c ) if a < bc
Note: Since k do not affect the result, they are sometimes not included in the above
recurrence

Example1: Find the big-Oh running time of the following recurrence. Use the Master
Theorem:

Solution: a = 3, b = 4, c = ½ → a > bc → Case 1

Hence 𝑇(𝑛) ∈ 𝑂(𝑛log4 3 )

Example2: Find the big-Oh running time of the following recurrence. Use the Master
Theorem:
T(1) = 1
T(n) = 2T(n / 2) + n
Solution: a = 2, b = 2, c = 1 → a = bc → Case 2
Hence T(n) is O(n log n)

Example3: Find the big-Oh running time of the following recurrence. Use the Master Theorem:
T(1) = 1
T(n) = 4T(n / 2) + kn3 + h where k ≥ 1 and h  1
Solution: a = 4, b = 2, c = 3 → a < bc → Case 3
Hence T(n) is O(n3)
Example4: Find the big-Oh running time of the following recurrence. Use the Master Theorem:
T(0) = 1 n=0
T(n) = 5 + T(n – 1) n>0
a=1, k=5 , c=0, b=1
Not that b is not ≥1 so we can’t use the Master Theorem
Example5: Analysis Of Recursive Binary Search Use the Master
public int binarySearch (int target, int[] array,
int low, int high) {
if (low > high)
return -1;
else {
int middle = (low + high)/2;
if (array[middle] == target)
return middle;
else if(array[middle] < target)
return binarySearch(target, array, middle + 1, high);
else
return binarySearch(target, array, low, middle - 1);
}
}
Binary search Find an element in a sorted array:
1. Divide: Check middle element.
2. Conquer: Recursively search 1subarray.
3. Combine: Trivial.
Example 4 : Find 9 in array 3 5 7 8 9 12 15
Steps
➢ 3 5 7 8 9 12 15
➢ 3 5 7 8 9 12 15
➢ 3 5 7 8 9 12 15
➢ 3 5 7 8 9 12 15
➢ 3 5 7 8 9 12 15
The recurrence relation for the running time of the method is:
T(1) = 1 if n = 1 (one element array)
T(n) = T(n / 2) + 4 if n > 1
Solution: a = 1, b = 2, c = 0 → a = bc → Case 2 Hence 𝑇(𝑛) ∈ 𝑂(𝑛c log 𝑛) = 𝑂(log 𝑛)
Analysis Of Recursive Merge Sort

Divide:
• [38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .

• [38, 27] is divided into [38] and [27] .

• [43, 10] is divided into [43] and [10] .
Conquer:
• [38] is already sorted.
• [27] is already sorted.
• [43] is already sorted.
• [10] is already sorted.
Merge:
• Merge [38] and [27] to get [27, 38] .
• Merge [43] and [10] to get [10,43] .

• Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]

Therefore, the sorted list is [10, 27, 38, 43] .

 void mergeSort (int arr[], int l, int r)
{
if (l < r)
{ int m = l + (r - l) / 2; // Find the middle point
mergeSort(arr, l, m); // Sort first and second halves
mergeSort(arr, m + 1, r);
merge(arr, l, m, r); // Merge the sorted halves
}
}
// Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{ // Find sizes of two subarrays to be merged
int n1 = m - l + 1; int n2 = r - m;
int L[] = new int[n1]; int R[] = new int[n2]; // Create temp arrays
// Copy data to temp arrays
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Merge the temp arrays
int i = 0, j = 0; // Initial indices of first and second subarrays
int k = 0; // Initial index of merged subarray array
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{ arr[k] = L[i];
i++;
}
else
{ arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) // Copy remaining elements of L[] if any
{ arr[k] = L[i];
i++; k++;
}
while (j < n2) // Copy remaining elements of R[] if any
{
arr[k] = R[j];
j++; k++;
}
}
Recurrence Relation of Merge Sort:
The recurrence relation of merge sort is:
T(1)= 1 if n=1
T(n) = 2T(n/2) + f(n) if n>1
• T(n) Represents the total time time taken by the algorithm to sort an array of size n.
• 2T(n/2) represents time taken by the algorithm to recursively sort the two halves of the
array. Since each half has n/2 elements, we have two recursive calls with input size as
(n/2).
• f(n) represents the time taken to merge the two sorted halves
• To merge the two sorted halves we do in O(n)
So Recurrence Relation of Merge Sort T(n) =2T(n/2) + kn
Using master method: a = 2, b = 2, c = 1 → a = bc →Case: 2 Hence T(n) is O(n log n)
• Time Complexity:
o Best Case: O(n log n), When the array is already sorted or nearly sorted.
o Average Case: O(n log n), When the array is randomly ordered.
o Worst Case: O(n log n), When the array is sorted in reverse order.