PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q10

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Introduction

Question

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 :

  1. Identify Input Size (): e.g., array length, number of nodes, or matrix dimension.
  2. 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 .
  3. Determine Input Cases: Analyze best case, average case, and worst case behavior.
  4. 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;
}
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.

All past exam questions for Data Structure and Algorithms