Purpose of Algorithm Analysis

• Determines how an algorithm's resource usage (time, space) scales as input size (n) grows — enables comparison independent of hardware/language

Time Complexity Cases

• Best case — minimum time (e.g., already-sorted array for insertion sort → O(n))
• Worst case — maximum time (most commonly reported/tested — guarantees an upper bound)
• Average case — expected time over all possible inputs (hardest to compute rigorously)

Worked Example: Best, Worst, and Average Case — Linear Search

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;   // found
    }
    return -1;                          // not found
}

• Best case: key is at index 0 — loop runs just 1 time → O(1).
• Worst case: key is at the last index, or absent entirely — loop runs all n times → O(n).
• Average case: assuming the key is equally likely at any of the n positions (and always present), expected comparisons = (1+2+…+n)/n = (n+1)/2 → still O(n) (the constant ½ drops out).

Key reasoning point: Big-O is quoted for the worst case unless a question specifically asks otherwise — Linear Search is described as "O(n)", not "O(1)", because O(n) is the guarantee holding for every possible input, not just a lucky one.

Exam angle: when FPSC asks for best/worst/average case complexity, always state a concrete input scenario for each ("best case: element already at index 0") rather than a vague description — examiners award marks for that concrete justification, not just the final O() label.

Space Complexity

• Total memory used by the algorithm: input storage + auxiliary/working space + call stack (relevant for recursive algorithms)

Empirical vs Theoretical Analysis

• A priori (theoretical): analyze algorithm mathematically before implementation — hardware-independent, the CSS-tested approach
• A posteriori (empirical): run the actual program and measure real time/memory — hardware-dependent, used for benchmarking

Exam Angle