LINEAR SEARCH, BINARY SEARCH, QUICK SORT, MERGE
SORT AND STRASSEN’S MATRIX MULTIPLICATION and
Time Complexity Analysis
Algorithm: Linear Search
1. Input an array A[0 .. n − 1] and the target element x.
2. For i = 0 to n − 1:
• If A[i] = x, then return i (element found).
3. If the loop finishes without finding x, return “not found”.
Time Complexity Analysis (Back Substitution Method)
Worst Case: The element is either absent or at the last position, so all n elements are compared.
T (n) = T (n − 1) + C (1)
Step 1: Start with the recurrence relation
T (n) = T (n − 1) + C
Step 2: Substitute for T (n − 1)
From (1):
T (n − 1) = T (n − 2) + C
Substitute into T (n):
T (n) = [T (n − 2) + C] + C
T (n) = T (n − 2) + 2C (2)
Step 3: Substitute for T (n − 2)
From (2):
T (n − 2) = T (n − 3) + C
Substitute:
T (n) = [T (n − 3) + C] + 2C
T (n) = T (n − 3) + 3C (3)
Step 4: Identify the pattern
After k substitutions:
T (n) = T (n − k) + kC (4)
1
Step 5: Stop when base case is reached
Base case: T (1) = C0 (constant time to check one element)
When n − k = 1 ⇒ k = n − 1
Substitute into (4):
T (n) = T (1) + (n − 1)C
T (n) = C0 + C(n − 1)
Step 6: Final Complexity
Ignoring constants:
T (n) = O(n)
Best case: O(1) (element found at first position)
Average case: O(n)
Binary Search Algorithm and Time Complexity Analysis
Algorithm: Binary Search
1. Input a sorted array A[0 .. n − 1] and a target element x.
2. Set low = 0, high = n - 1.
3. While low ≤ high:
• Compute mid index: m = ⌊(low + high)/2⌋.
• If A[m] = x, return m.
• If A[m] < x, set low = m + 1.
• Else, set high = m − 1.
4. If loop ends, return “not found”.
Time Complexity Analysis (Back Substitution Method)
Worst Case: The array is divided into two halves at each step until only one element remains.
n
T (n) = T +C (1)
2
Step 1: Start with the recurrence relation
n
T (n) = T +C
2
n
Step 2: Substitute for T 2
From (1): n n
T =T +C
2 4
Substitute into T (n): h n i
T (n) = T +C +C
4
n
T (n) = T + 2C (2)
4
2
n
Step 3: Substitute for T 4
From (2): n n
T =T +C
4 8
Substitute: h n i
T (n) = T + C + 2C
8
n
T (n) = T + 3C (3)
8
Step 4: Identify the pattern
After k substitutions: n
T (n) = T + kC (4)
2k
Step 5: Stop when base case is reached
Base case: T (1) = C0
Condition:
n
=1 ⇒ n = 2k ⇒ k = log2 n
2k
Substitute into (4):
T (n) = T (1) + C log2 n
T (n) = C0 + C log2 n
Step 6: Final Complexity
Ignoring constants:
T (n) = O(log n)
Best case: O(1) (middle element matches in first step)
Average/Worst case: O(log n)
Quick Sort Algorithm and Time Complexity Analysis
Algorithm: Quick Sort
1. Input an array A[0 .. n − 1].
2. If n ≤ 1, return (array is already sorted).
3. Choose a pivot element p (commonly the first, last, or a random element).
4. Partition the array into two subarrays:
• Left subarray: elements < p
• Right subarray: elements ≥ p
5. Recursively apply Quick Sort to both subarrays.
6. Combine results to get the sorted array.
Time Complexity Analysis (Back Substitution Method)
Best/Average Case: The pivot divides the array into two equal halves.
n
T (n) = 2T + Cn (1)
2
3
Step 1: Start with the recurrence relation
n
T (n) = 2T + Cn
2
n
Step 2: Substitute for T 2
From (1): n n n
T = 2T +C
2 4 2
Substitute into T (n): h n ni
T (n) = 2 2T +C + Cn
4 2
n
T (n) = 4T + Cn + Cn
4
n
T (n) = 4T + 2Cn (2)
4
n
Step 3: Substitute for T 4
From (2): n n
n
T = 2T +C
4 8 4
Substitute: h n ni
T (n) = 4 2T +C + 2Cn
8 4
n
T (n) = 8T + Cn + 2Cn
8
n
T (n) = 8T + 3Cn (3)
8
Step 4: Identify the pattern
After k substitutions: n
T (n) = 2k T + kCn (4)
2k
Step 5: Stop when base case is reached
Base case: T (1) = C0
Condition:
n
=1 ⇒ k = log2 n
2k
Substitute into (4):
T (n) = 2log2 n · T (1) + Cn log2 n
T (n) = n · C0 + Cn log2 n
Step 6: Final Complexity
Ignoring constants:
T (n) = O(n log n)
Best/Average case: O(n log n)
Worst case: O(n2 ) (if pivot always splits poorly)
4
Algorithm: Merge Sort
1. Input an array A[0 .. n − 1].
2. If n ≤ 1, return (array is already sorted).
3. Divide the array into two halves.
4. Recursively apply Merge Sort to each half.
5. Merge the two sorted halves into a single sorted array.
Time Complexity Analysis (Back Substitution Method)
Worst/Average Case: The array is always divided into two equal halves, and merging takes O(n) time.
n
T (n) = 2T + Cn (1)
2
Step 1: Start with the recurrence relation
n
T (n) = 2T + Cn
2
n
Step 2: Substitute for T 2
From (1): n n n
T = 2T +C
2 4 2
Substitute into T (n): h n ni
T (n) = 2 2T +C + Cn
4 2
n
T (n) = 4T + Cn + Cn
4
n
T (n) = 4T + 2Cn (2)
4
n
Step 3: Substitute for T 4
From (2): n n n
T = 2T +C
4 8 4
Substitute: h n ni
T (n) = 4 2T +C + 2Cn
8 4
n
T (n) = 8T + Cn + 2Cn
8
n
T (n) = 8T + 3Cn (3)
8
Step 4: Identify the pattern
After k substitutions: n
T (n) = 2k T + kCn (4)
2k
5
Step 5: Stop when base case is reached
Base case: T (1) = C0
Condition:
n
=1 ⇒ k = log2 n
2k
Substitute into (4):
T (n) = 2log2 n · T (1) + Cn log2 n
T (n) = n · C0 + Cn log2 n
Step 6: Final Complexity
Ignoring constants:
T (n) = O(n log n)
Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n)
Algorithm: Strassen’s Matrix Multiplication
1. Input two n × n matrices A and B.
2. If n = 1, multiply the two numbers directly.
3. Otherwise:
n n
(a) Divide A and B into four 2 × 2 submatrices.
(b) Compute the following 7 products recursively:
M1 = (A11 + A22 )(B11 + B22 )
M2 = (A21 + A22 )B11
M3 = A11 (B12 − B22 )
M4 = A22 (B21 − B11 )
M5 = (A11 + A12 )B22
M6 = (A21 − A11 )(B11 + B12 )
M7 = (A12 − A22 )(B21 + B22 )
(c) Combine the Mi results to get the final matrix product.
Time Complexity Analysis (Back Substitution Method)
Observation: The recurrence relation is:
n
T (n) = 7T + Cn2 (1)
2
Step 1: Start with the recurrence relation
n
T (n) = 7T + Cn2
2
6
n
Step 2: Substitute for T 2
From (1):
n n n 2
T = 7T +C
2 4 2
Substitute into T (n):
n2
n
T (n) = 7 7T +C + Cn2
4 4
n 7Cn2
T (n) = 49T + + Cn2
4 4
n 11Cn2
T (n) = 49T + (2)
4 4
n
Step 3: Substitute for T 4
From (2):
n n n 2
T = 7T +C
4 8 4
Substitute:
n2 11Cn2
n
T (n) = 49 7T +C +
8 16 4
n 49Cn2 11Cn2
T (n) = 343T + +
8 16 4
n 49Cn2 + 44Cn2
T (n) = 343T +
8 16
n 93Cn2
T (n) = 343T + (3)
8 16
Step 4: Identify the pattern
After k substitutions:
n k−1
X 7i
T (n) = 7k T + Cn2
· (4)
2k i=0
4i
Step 5: Stop when base case is reached
Base case: T (1) = C0
Condition:
n
=1 ⇒ k = log2 n
2k
Substitute into (4):
log2 n−1 i
log2 n 2
X 7
T (n) = 7 · T (1) + Cn ·
i=0
4
Since:
7log2 n = nlog2 7 where log2 7 ≈ 2.8074
The geometric sum is dominated by the largest term, giving:
T (n) = Θ nlog2 7 ≈ Θ n2.8074
Step 6: Final Complexity
T (n) = O nlog2 7 ≈ O n2.81
Strassen’s improvement: Faster than O(n3 ) of naive multiplication.
