Design and Analysis of Algorithm
Quiz-01 (Fall 2024)
Name: _______________________ Roll No: ______________ Time: 20 minutes
Instructor: Dr. Tanweer Bukhari Section: E06 Marks: 15
Task 1 : Time Complexity Analysis
void AlgorithmA(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int AlgorithmB(int arr[], int target, int start = 0) {
if (start >= size(arr)) {
return -1;
}
if (arr[start] == target) {
return start;
}
return AlgorithmB(arr, target, start + 2);
}
Identify the time complexity and the operations being performed by each algorithm.
Algorithm A Algorithm B
Best Case Complexity O(n) O(1)
Worst Case Complexity O(n2) O(n)
Operation Insertion Sort (Iterative) Linear Search (Recursive)
Recursive Relation N/A T(n) – T(n-1) + 1
Task 2: Recursive Algorithm Analysis
Consider the following recursive algorithm:
void RecursiveFunction(int n) {
if (n <= 1) {
return;
}
RecursiveFunction(n / 3);
RecursiveFunction(n / 3);
RecursiveFunction(n / 3);
}
a) Write the recursive equation for T(n).
𝑛
Solution: 𝑇(𝑛) = 3𝑇 ( 3) + 1
Faculty of Information Technology
University of Central Punjab
Lahore, Pakistan
