Past exam question: 2078 Chaitra (Regular), Q10
Open in the Padhaiko appQuestion
How do you find complexity of any algorithm? Explain with suitable example.
Solution
Steps to Determine Algorithm Complexity: Algorithm complexity measures the time (number of elementary operations) and space (auxiliary memory) required as a function of input size :
- Identify Input Size (): e.g., array length, number of nodes, or matrix dimension.
- Count Primitive Operations: Assign unit cost to basic statements (assignments, comparisons, arithmetic, array indexing) and sum loop/recursion execution counts as a frequency count function .
- Determine Input Cases: Analyze best case, average case, and worst case behavior.
- Drop Constants & Lower-Order Terms: Express the growth rate using asymptotic notation (, , ).
Example: Linear Search in an Array of Size :
int linearSearch(int A[], int n, int key) {
for (int i = 0; i < n; i++) { // runs at most n+1 checks
if (A[i] == key) // runs at most n comparisons
return i;
}
return -1;
}
- Best Case:
keyis atA[0]comparison . - Worst Case:
keyis atA[n-1]or absent comparisons, time. - Space Complexity: Only loop variable
iis allocated auxiliary space.
Answer:
Complexity is found by expressing the count of dominant primitive operations as a function of input size (across best, average, and worst cases) and simplifying to its asymptotic growth order (). For linear search, worst-case gives time and space.