2.2 ~35 min easy

Measuring Efficiency

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

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental 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:

Redundant computation: computing the same value again and again inside a loop. Move it out of the loop.
Late loop termination: continuing to loop after the answer is already known. break or return early.
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.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Search for a value near the front, then for one that is missing. When does breaking early help?

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

fixing the three inefficiencies49 lines · C++17

Compiler ExplorerRun OnlineGDB

#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";
}

#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

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

05Complexity

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.

06Watch

Time Complexity #1

Abdul Bari · 9:44

Why this one: Explains why we count steps instead of timing with a stopwatch.

Watched

Big O Notation

HackerRank · 8:36

Why this one: A short, clear intuition for why growth rate matters more than exact seconds.

Watched

07Exam 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.

08Quick check

1.Running two programs and timing them with a stopwatch is…
2.Readability, simplicity and maintainability are part of…
3.Which inefficiency is in this loop?
```
for (int i = 0; i < n; i++)
    total += a[i] * sqrt(x);
```
4.Using a hash set to find duplicates in O(n) instead of O(n²) is an example of…

09Practice

🟢 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).

Show answer

Redundant computation: k * k / 2 is recomputed every iteration; compute half = k*k/2 once.
Repeated array referencing: a[i] is read twice; store it in int v = a[i];.
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.

🔴 Solve problems

Contains Duplicate easyleetcode.com
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 easyleetcode.com
Hint
The textbook time–space trade-off. Write the O(n²) version first, then the hash-map version.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

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.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet