# 2.2 Measuring Efficiency

> Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.

Chapter: Algorithm & Algorithm Analysis · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/analysis-approaches

## Mental model

How do you decide which of two algorithms is "better"? There are two ways to find out.

### Empirical vs theoretical

- **Empirical analysis** = *run it and measure*. Implement both, time them on test data. It is easy to understand, but the result depends on the **computer, compiler, language, other running programs and the inputs you chose**. A fast laptop can make a bad algorithm look good.
- **Theoretical analysis** = *count the steps on paper* as a function of the input size **n**. It is independent of the machine and covers **all** inputs. This is what the rest of the chapter teaches.

### Qualitative vs quantitative

- **Qualitative**: Is it simple? Readable? Easy to maintain and modify? Does it handle errors?
- **Quantitative**: How much **time** (number of operations) and **space** (memory) does it use?

### Avoidable inefficiencies

These are "free" speed-ups that don't change the algorithm's idea:

1. **Redundant computation**: computing the same value again and again inside a loop. Move it out of the loop.
2. **Late loop termination**: continuing to loop after the answer is already known. `break` or `return` early.
3. **Repeated array referencing**: reading `a[i]` several times in one iteration. Read it once into a local variable.

### The time–space trade-off

You can often buy speed with memory: a lookup table, a set of seen values, a prefix-sum array. Or save memory by recomputing. Good design picks the balance the problem needs. On a phone with little memory you may choose differently than on a server.

## C++ code: fixing the three inefficiencies

```cpp
#include <iostream>
using namespace std;

int checks = 0;

// Late termination: keeps looping after the answer is known.
bool containsSlow(const int a[], int n, int key) {
    bool found = false;
    for (int i = 0; i < n; i++) {
        checks++;
        if (a[i] == key) found = true;
    }
    return found;
}

// Fixed: stop as soon as we know.
bool containsFast(const int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        checks++;
        if (a[i] == key) return true;
    }
    return false;
}

int main() {
    int a[] = {5, 12, 8, 3, 19, 7, 25, 11};
    int n = 8;

    checks = 0; containsSlow(a, n, 8);
    cout << "slow: " << checks << " checks\n";
    checks = 0; containsFast(a, n, 8);
    cout << "fast: " << checks << " checks\n";

    // Redundant computation: x*x is recomputed on every pass
    double x = 3, total = 0;
    for (int i = 0; i < 4; i++) total += a[i] * (x * x);
    // Better: compute it once, outside the loop
    double x2 = x * x, total2 = 0;
    for (int i = 0; i < 4; i++) total2 += a[i] * x2;
    cout << "same result: " << total << " == " << total2 << "\n";

    // Repeated array referencing: read a[i] once into a local variable
    int best = a[0];
    for (int i = 1; i < n; i++) {
        int v = a[i];            // one reference instead of two
        if (v > best) best = v;
    }
    cout << "max = " << best << "\n";
}
```

Expected output:

```text
slow: 8 checks
fast: 3 checks
same result: 252 == 252
max = 25
```

## Complexity

| Case | Cost |
| --- | --- |
| Search with late termination | always n checks |
| Search that breaks early | 1 … n checks |
| Duplicate check with nested loops | O(n²) time, O(1) space |
| Duplicate check with a set | O(n) time, O(n) space ← trade-off |


Trading memory for speed (or the reverse) is the **time–space trade-off**. Neither side is free.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Explains why we count steps instead of timing with a stopwatch.
- [Big O Notation](https://youtu.be/v4cd1O4zkGw) (HackerRank): A short, clear intuition for why growth rate matters more than exact seconds.

## Exam lens

Likely questions:

- Compare empirical and theoretical analysis. Give two drawbacks of empirical analysis.
- What is the difference between qualitative and quantitative analysis of an algorithm?
- Explain three avoidable inefficiencies with a code example of each.
- Explain the time–space trade-off with an example.

Common mistakes:

- Saying empirical analysis is useless. It is useful, but its results depend on the machine, compiler, language and inputs.
- Mixing up "redundant computation" (recomputing the same value in a loop) with "repeated array referencing" (reading `a[i]` many times).
- Thinking the faster algorithm is always better. It may need far more memory.

## Quick check

1. Running two programs and timing them with a stopwatch is…
   A. theoretical analysis
   B. empirical analysis
   C. asymptotic analysis
   D. qualitative analysis
   Answer: B. Empirical = by experiment. Results depend on hardware, compiler and test inputs.

2. Readability, simplicity and maintainability are part of…
   A. quantitative analysis
   B. qualitative analysis
   C. empirical analysis
   D. Big-O analysis
   Answer: B. Qualitative analysis judges the quality of the design. Quantitative analysis measures time and space numerically.

3. Which inefficiency is in this loop?

```cpp
for (int i = 0; i < n; i++)
    total += a[i] * sqrt(x);
```
   A. Late termination
   B. Redundant computation
   C. Repeated array referencing
   D. None
   Answer: B. `sqrt(x)` never changes, but it is recomputed n times. Compute it once before the loop.

4. Using a hash set to find duplicates in O(n) instead of O(n²) is an example of…
   A. the time–space trade-off
   B. late termination
   C. empirical analysis
   D. definiteness
   Answer: A. We spend O(n) extra memory to save time.

## Practice

**Trace by hand.** Spot every avoidable inefficiency: `for (i = 0; i < n; i++) { if (a[i] > a[i] * k * k / 2) found = true; }` (we only need to know whether at least one such item exists).

Solution:

1. **Redundant computation**: `k * k / 2` is recomputed every iteration; compute `half = k*k/2` once.
2. **Repeated array referencing**: `a[i]` is read twice; store it in `int v = a[i];`.
3. **Late termination**: once `found` is true we should `break`.


**Implement it.** Write a program that checks whether an array has two equal items in two ways (nested loops, and a `std::set`). Count the comparisons each method makes on 1000 random numbers.

Hint: Use a global counter, incremented before each comparison. Nested loops make about n²/2 comparisons.

**Problems:**

- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). Hint: Brute force is O(n²) time and O(1) space. A set is O(n) time and O(n) space. Sorting first is O(n log n) time with little extra space. Three points on the trade-off curve.
- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). Hint: The textbook time–space trade-off. Write the O(n²) version first, then the hash-map version.

## Mastery checklist

- [ ] I can compare empirical and theoretical analysis.
- [ ] I can explain qualitative vs quantitative analysis.
- [ ] I can spot and fix redundant computation, late termination and repeated array referencing.
- [ ] I can explain the time–space trade-off with an example.