2.3 ~50 min medium

Counting Time Units

Turn code into a formula T(n) using the instructor's counting rules. Loops become sums, and nested loops multiply.

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

02Mental model

Instead of timing code with a stopwatch, we count operations. Each simple operation costs 1 time unit. Then T(n), the total as a function of input size n, tells us how the work grows.

The rules (use exactly these on the exam)

1 unit each for: an assignment, a single input/output, a Boolean operation (<, ==, &&, …), an arithmetic operation (+, -, *, /, %, ++), and a return.
if / switch: time of the condition + the time of the largest branch.
Loops: the loop header costs 1 (initialization) + (n + 1) (tests: n true plus one false) + n (increments). The body costs (body time) × (number of iterations).
Nested loops: multiply. The inner body runs (outer iterations) × (inner iterations) times.
Function call: 1 (call setup) + the parameters + the time of the body.

Worked example

for (i = 0; i < n; i++)
    k = k + 1;
cout << k;

Part	Units
`i = 0`	1
`i < n`	n + 1
`i++`	n
`k = k + 1` (add + assign)	2n
`cout << k`	1

$T(n) = 1 + (n+1) + n + 2n + 1 = 4n + 3$

Loops → summations

When the inner loop depends on the outer variable, write the count as a sum:

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;

The body runs $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ times, so it grows like n².

Three sums to memorise:

$\sum_{i=1}^{n} 1 = n$
$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

03Visualize

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

Loading visualizer…

Change n and watch each rule add its units.

Loading visualizer…

04C++ code

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

counting by instrumenting the code48 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

// We count time units with the instructor's rules by adding to `t`
// next to each operation, then compare with the formula T(n) = 4n + 3.
long long countLoop(int n) {
    long long t = 0;
    int k = 0;
    int i;
    t++; i = 0;                  // 1 assignment (init)
    while (true) {
        t++;                     // 1 test: i < n
        if (!(i < n)) break;
        t += 2; k = k + 1;       // add + assign
        t++; i++;                // 1 increment
    }
    t++; (void)k;                // cout << k: 1 output
    return t;
}

long long countNested(int n) {
    long long t = 0;
    int k = 0;
    t++;                                     // k = 0
    t++;                                     // i = 0
    for (int i = 0; ; i++) {
        t++;                                 // i < n
        if (!(i < n)) break;
        t++;                                 // j = 0
        for (int j = 0; ; j++) {
            t++;                             // j < n
            if (!(j < n)) break;
            t++; k++;                        // k++
            t++;                             // j++
        }
        t++;                                 // i++
    }
    return t;
}

int main() {
    for (int n : {1, 3, 10}) {
        cout << "n=" << n << "  loop: counted " << countLoop(n)
             << ", 4n+3 = " << 4 * n + 3
             << "  |  nested: counted " << countNested(n)
             << ", 3n^2+4n+3 = " << 3 * n * n + 4 * n + 3 << "\n";
    }
}

#include <iostream>
using namespace std;

// We count time units with the instructor's rules by adding to `t`
// next to each operation, then compare with the formula T(n) = 4n + 3.
long long countLoop(int n) {
    long long t = 0;
    int k = 0;
    int i;
    t++; i = 0;                  // 1 assignment (init)
    while (true) {
        t++;                     // 1 test: i < n
        if (!(i < n)) break;
        t += 2; k = k + 1;       // add + assign
        t++; i++;                // 1 increment
    }
    t++; (void)k;                // cout << k: 1 output
    return t;
}

long long countNested(int n) {
    long long t = 0;
    int k = 0;
    t++;                                     // k = 0
    t++;                                     // i = 0
    for (int i = 0; ; i++) {
        t++;                                 // i < n
        if (!(i < n)) break;
        t++;                                 // j = 0
        for (int j = 0; ; j++) {
            t++;                             // j < n
            if (!(j < n)) break;
            t++; k++;                        // k++
            t++;                             // j++
        }
        t++;                                 // i++
    }
    return t;
}

int main() {
    for (int n : {1, 3, 10}) {
        cout << "n=" << n << "  loop: counted " << countLoop(n)
             << ", 4n+3 = " << 4 * n + 3
             << "  |  nested: counted " << countNested(n)
             << ", 3n^2+4n+3 = " << 3 * n * n + 4 * n + 3 << "\n";
    }
}

Expected output

n=1  loop: counted 7, 4n+3 = 7  |  nested: counted 10, 3n^2+4n+3 = 10
n=3  loop: counted 15, 4n+3 = 15  |  nested: counted 42, 3n^2+4n+3 = 42
n=10  loop: counted 43, 4n+3 = 43  |  nested: counted 343, 3n^2+4n+3 = 343

05Complexity

Single loop `for(i=0;i<n;i++) k=k+1; cout<<k;`	T(n) = 4n + 3 → O(n)
Nested n × n loop with `k++`	T(n) = 3n² + 4n + 3 → O(n²)
Loop where i doubles (`i *= 2`)	≈ log₂ n iterations → O(log n)

The exact T(n) depends on the counting rules; the growth rate (Big-O) does not. Use your instructor's rules on the exam.

06Watch

Time Complexity #1

Abdul Bari · 9:44

Why this one: Abdul Bari counts statements in loops step by step, the same skill as here.

Watched

07Exam lens

Likely questions

Calculate T(n) for: int k=0; for(int i=0;i<n;i++) k=k+1; cout<<k;
Calculate T(n) for a nested loop where both loops run n times and the body is sum++.
Express the loop for(i=1;i<=n;i++) for(j=1;j<=i;j++) x++; as a summation and simplify it.
State the counting rules for if-statements, loops and function calls.

Common mistakes

Counting the loop test n times instead of n + 1 (the last, failing test counts too).
Counting k = k + 1 as 1 unit. It is 2: one addition and one assignment.
For if/else, adding both branches. Count the condition plus the larger branch only.
Forgetting the initialization of the loop (1 unit, done once).

08Quick check

1.Using the course rules, T(n) for for(i=0;i<n;i++) k=k+1; cout<<k; is:
2.How many times is the condition i < n evaluated in for (i = 0; i < n; i++)?
3.An if (x > 0) a = b + c; else a = 0; costs:
4.The summation $\sum_{i=1}^{n} i$ equals:
5.What is the order of growth of for (i = 1; i < n; i *= 2) count++;?

09Practice

🟢 Trace by hand

Compute T(n) with the course rules:

int sum = 0;
for (int i = 0; i < n; i++)
    sum = sum + i;
return sum;

Show answer

sum = 0: 1
loop: 1 (init) + (n + 1) (tests) + n (increments)
body sum = sum + i: 2 per iteration → 2n
return sum: 1

T(n) = 1 + 1 + (n+1) + n + 2n + 1 = 4n + 4 → O(n)

🟡 Implement it

Add a global long long t counter to selectionSort that counts every comparison and assignment. Print t for n = 10, 100, 1000 and check that it grows like n².

Hint

When n is ×10, a quadratic count should be ≈ ×100.

🔴 Solve problems

Count Odd Numbers in an Interval Range easyleetcode.com
Hint
A loop from low to high is O(n). Can you find a formula that is O(1)? Count units for both versions.

Solution idea
(high + 1) / 2 - low / 2, a constant number of operations.
Sqrt(x) easyleetcode.com
Hint
Trying i = 1, 2, 3… is O(√x). Binary search over [0, x] is O(log x). Count iterations of each for x = 10⁶.

10Mastery checklist

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

I can apply the counting rules for assignments, I/O, operators, if, loops and calls.
I can get T(n) = 4n + 3 for the standard single loop without notes.
I can count a nested loop and write it as a summation.
I can simplify Σ1, Σi and Σi² sums.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet