CMP 413: Algorithm and Complexity
Analysis
Session: 2023/2024
Exam Answers (Questions 1 to 5)
Question 1
State the insertion sort algorithm and considering the following datasets, answer the
following questions:
Insertion Sort Algorithm:
for i from 1 to n-1:
key = A[i]
j=i-1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j=j-1
A[j + 1] = key
Datasets and Required Ordering:
Scenario 1: [40, 25, 35, 37, 5] (Order: ascending)
Scenario 2: [5, 7, 12, 18, 19, 20] (Order: ascending)
Scenario 3: [40, 25, 12, 10, 5] (Order: descending)
Functional Values:
The functional values for each scenario depend on the number of comparisons and shifts
required by the insertion sort algorithm given the ordering requirement.
Scenario 1:
Dataset: [40, 25, 35, 37, 5] - Ascending order
- This dataset is unsorted, so the algorithm must move elements several times.
- Functional time is close to the worst case (O(n²)) due to many shifts.
- Number of comparisons and shifts are high.
Scenario 2:
Dataset: [5, 7, 12, 18, 19, 20] - Ascending order
- Dataset is already sorted.
- The algorithm performs minimal comparisons, no shifts needed.
- Functional time is best case: O(n).
Scenario 3:
Dataset: [40, 25, 12, 10, 5] - Descending order
- Since the dataset is already in descending order and the required ordering is descending,
the algorithm will find the array sorted as required.
- Functional time is best case: O(n).
Table of Functional Values:
Scenario Number of Number of Shifts Time Complexity
Comparisons
Scenario 1 10 (approx) 10 (approx) O(n²)
Scenario 2 5 (approx) 0 O(n)
Scenario 3 5 (approx) 0 O(n)
Discussion on Efficiency:
Insertion sort is efficient for small or nearly sorted datasets due to its low overhead and
linear performance in the best case. However, it performs poorly on large, reverse-ordered
datasets where the time complexity approaches O(n²). Hence, its efficiency depends greatly
on the initial ordering of the dataset.
Question 2
State the pseudocodes of the bubblesort algorithm and suggest a dataset with n>=10, typical
of the worst case scenario of the algorithm.
Bubble Sort Pseudocode:
for i from 0 to n-1:
for j from 0 to n-i-1:
if A[j] > A[j+1]:
swap A[j] and A[j+1]
Worst Case Dataset:
A = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11] (Reverse sorted, n=10)
Performance Analysis:
In the worst case, bubble sort performs the maximum number of comparisons and swaps.
Comparisons per pass are: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
Total comparisons = 45
Question 3
The performance of binary search depends on the number of binary partitions the
algorithm does before finding the search item. Given a data set of integers with size n=129,
use mathematical induction to show that for certain values of n, f(n) = log n and for others,
f(n) = log(n) - 1.
Subsequently, derive the O-notation for the binary search algorithm showing appropriate
values of c₀ and n₀ and depict same in a graphical representation.
For n = 129:
⌊log₂(129)⌋ = 7
The function f(n) behaves as follows:
- f(n) = log₂(n) when n is a power of 2
- f(n) = ⌊log₂(n)⌋ when n is not a power of 2
Mathematical induction shows that for values n = 2^k (powers of 2), f(n) = k = log₂(n).
For other values, f(n) = ⌊log₂(n)⌋ = k or k - 1 depending on the range.
Derivation of O-Notation:
f(n) ≤ c₀ * log₂(n), choose c₀ = 1 and n₀ = 1
Therefore, f(n) = O(log₂(n))
Question 4
State the sequential algorithm and use a data set with size n>= 6 representing the worst-
case scenario of the algorithm to derive a histogram representing the work done by the
algorithm.
Enumerate all the family of functions associated with a sequential search on the dataset if
possible, else apply a mathematical technique of your choice to derive the work done by the
algorithm in the average case scenario.
Generate a data set with size n>=6 representing the best-case scenario and derive the work
done by the algorithm.
Sequential Search Algorithm:
Given dataset A of size n, to find data:
for i from 0 to n-1:
if A[i] == data:
return i
return -1 (if not found)
Worst Case Dataset:
A = [3, 5, 7, 8, 10, 12] (Searching for 14, which is not in the list)
Work Done:
- Worst-case comparisons = 6 (all elements checked)
- Average-case comparisons = 3.5 (average position)
- Best-case comparisons = 1 (first element)
Question 5
Consider searching the array dataset A = {1, 2, 4, 8, 10, 12, 14, 18} using the binary search
algorithm.
Case 1: Searching for 18 (Actual Index 7)
Step 1: mid = 3 → A[3] = 8
Step 2: mid = 5 → A[5] = 12
Step 3: mid = 6 → A[6] = 14
Step 4: mid = 7 → A[7] = 18 → Found
Total comparisons: 4
Case 2: Assuming 18 is at Position 4 (A[3])
Step 1: mid = 3 → A[3] = 18 → Found
Total comparisons: 1