# 2.3 Counting Time Units

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

Chapter: Algorithm & Algorithm Analysis · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/counting-time-units

## Mental 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. **1 unit** each for: an assignment, a single input/output, a Boolean operation (`<`, `==`, `&&`, …), an arithmetic operation (`+`, `-`, `*`, `/`, `%`, `++`), and a `return`.
2. **if / switch**: time of the condition **+ the time of the largest branch**.
3. **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)*.
4. **Nested loops**: multiply. The inner body runs (outer iterations) × (inner iterations) times.
5. **Function call**: **1** (call setup) **+ the parameters + the time of the body**.

### Worked example

```cpp
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:

```cpp
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}$

## C++ code: counting by instrumenting the code

```cpp
#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:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Abdul Bari counts statements in loops step by step, the same skill as here.

## Exam 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).

## Quick check

1. Using the course rules, T(n) for `for(i=0;i<n;i++) k=k+1; cout<<k;` is:
   A. 3n + 2
   B. 4n + 3
   C. 4n + 2
   D. 2n + 3
   Answer: B. 1 (init) + (n+1) tests + n increments + 2n (add + assign) + 1 (cout) = 4n + 3.

2. How many times is the condition `i < n` evaluated in `for (i = 0; i < n; i++)`?
   A. n − 1
   B. n
   C. n + 1
   D. 2n
   Answer: C. True n times plus the final false test.

3. An `if (x > 0) a = b + c; else a = 0;` costs:
   A. 1 + 2 + 1 = 4
   B. 1 + 2 = 3
   C. 2 + 1 = 3
   D. 1
   Answer: B. Condition (1) + the larger branch (`a = b + c` = 2).

4. The summation $\sum_{i=1}^{n} i$ equals:
   A. n
   B. n²
   C. n(n+1)/2
   D. 2ⁿ
   Answer: C. Gauss's formula. It is why a loop whose inner part runs i times is O(n²).

5. What is the order of growth of `for (i = 1; i < n; i *= 2) count++;`?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n log n)
   Answer: B. i takes values 1, 2, 4, 8, … so it reaches n after about log₂ n iterations.

## Practice

**Trace by hand.** Compute T(n) with the course rules:
```cpp
int sum = 0;
for (int i = 0; i < n; i++)
    sum = sum + i;
return sum;
```


Solution:

- `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.

**Problems:**

- [Count Odd Numbers in an Interval Range](https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/) (easy). Hint: A loop from low to high is O(n). Can you find a formula that is O(1)? Count units for both versions.
- [Sqrt(x)](https://leetcode.com/problems/sqrtx/) (easy). 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⁶.

## Mastery checklist

- [ ] 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.