📊 Performance Analysis

After completing this level, you should be able to:

• Identify input size and the basic operation of an algorithm.
• Count operations and express time complexity as a function of input size.
• Distinguish best, average and worst-case performance.
• Use Big-O, Big-Omega and Big-Theta notation correctly.
• Calculate auxiliary space and recursion-stack space.
• Explain the complexity of common loop and recursive patterns.

Performance analysis studies how the resources required by an algorithm grow when the input becomes larger. The main resources are execution time and memory space.

First decide what n represents. Then identify the operation that dominates the running time.

Time complexity is a function T(n) describing how the number of basic operations grows with input size n.

int first = a[0];
printf("%d", first);

for (int i = 0; i < n; i++) {
    sum += a[i];
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}

for (int value = n; value > 1; value /= 2) {
    count++;
}

Asymptotic analysis focuses on the dominant term as n becomes large. Constants and lower-order terms do not change the growth class.

Space complexity measures memory used as a function of input size. Auxiliary space is additional memory apart from the input.

long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

This program counts comparisons for the same key. Binary search requires a sorted array.

#include <stdio.h>

int linearSearch(int a[], int n, int key, int *count) {
    for (int i = 0; i < n; i++) {
        (*count)++;
        if (a[i] == key) return i;
    }
    return -1;
}

int binarySearch(int a[], int n, int key, int *count) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        (*count)++;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main(void) {
    int n, key;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &key);

    int linearCount = 0, binaryCount = 0;
    int linearIndex = linearSearch(a, n, key, &linearCount);
    int binaryIndex = binarySearch(a, n, key, &binaryCount);

    printf("Linear Search: index = %d, comparisons = %d\n", linearIndex, linearCount);
    printf("Binary Search: index = %d, comparisons = %d\n", binaryIndex, binaryCount);
    return 0;
}

8
4 9 13 18 25 31 42 57
42

Linear Search: index = 6, comparisons = 7
Binary Search: index = 6, comparisons = 3

Trace the sample program one statement at a time and compare how both searches locate key 42.

int a[] = {4, 9, 13, 18, 25, 31, 42, 57};
for (int i = 0; i < n; i++) {
    linearCount++;
    if (a[i] == key) return i;
int low = 0, high = n - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    binaryCount++;
    if (a[mid] == key) return mid;
    if (a[mid] < key) low = mid + 1;
    else high = mid - 1;

—

• Explain the reason: state how many times the dominant operation executes.
• Mention assumptions: sorted input, balanced trees and uniform hashing can change complexity.
• Separate time and space: an in-place algorithm may use little memory but still run slowly.
• Discuss trade-offs: extra memory or preprocessing may reduce repeated-query time.
• Use tight bounds: state Θ when upper and lower growth match.

• Performance analysis studies resource growth as input size increases.
• Time counts dominant operations; space counts growing memory.
• Big-O is an upper bound, Ω is a lower bound and Θ is a tight bound.
• Sequential costs add; nested iteration counts multiply.
• Repeated doubling or halving usually gives logarithmic complexity.
• Recursive algorithms may consume call-stack space.
• Amortized analysis distributes occasional expensive operations across a sequence.