Analysing Loops & Recursive Code

#Independent loops

Count the iterations of each loop and multiply when they are nested:

for (int i = 0; i < n; i++)          // n times
    for (int j = 0; j < m; j++)      // m times each
        work();                      // total n·m → O(nm)

#Dependent loops: sum the iterations

When the inner loop depends on the outer one, add up its iteration counts:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)     // runs i times
        work();

Total = 1 + 2 + … + n = n(n + 1)/2 = Θ(n²).

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)  // runs about n/i times
        work();

Total = n/1 + n/2 + … + n/n = n·(1 + 1/2 + … + 1/n) ≈ n ln n = Θ(n log n) (the harmonic series).

#Logarithmic loops

A loop variable that is multiplied or divided by a constant each step runs Θ(log n) times:

for (int i = 1; i < n; i *= 2) work();       // log2 n iterations
for (int i = n; i > 0; i /= 3) work();       // log3 n iterations
for (int i = 2; i < n; i = i * i) work();    // log log n iterations

#Measure it yourself

#include <cstdio>

int main() {
    for (long n = 1000; n <= 1000000; n *= 10) {
        long a = 0, b = 0, c = 0, d = 0;
        for (long i = 1; i < n; i *= 2) a++;                         // log n
        for (long i = 1; i <= n; i++) for (long j = 1; j <= n; j += i) b++;   // n log n (harmonic)
        for (long i = 2; i < n; i = i * i) c++;                      // log log n
        for (long i = 1; i * i <= n; i++) d++;                       // sqrt n
        printf("n=%8ld  log:%3ld  harmonic:%9ld  loglog:%2ld  sqrt:%5ld\n", n, a, b, c, d);
    }
    return 0;
}

n=    1000  log: 10  harmonic:     8053  loglog: 4  sqrt:   31
n=   10000  log: 14  harmonic:   103643  loglog: 4  sqrt:  100
n=  100000  log: 17  harmonic:  1266714  loglog: 5  sqrt:  316
n= 1000000  log: 20  harmonic: 14969985  loglog: 5  sqrt: 1000

#Common patterns

#Recursive code: write a recurrence

For a recursive function, write T(n) in terms of T on smaller inputs plus the work done outside the recursive calls:

The next lesson shows how to solve recurrences like these.

#Best, worst and average case

For linear search on n items:

• Best case: key at position 1 → 1 comparison → Θ(1).
• Worst case: key absent → n comparisons → Θ(n).
• Average case: if the key is equally likely to be at any position, expected comparisons = (1 + 2 + … + n)/n = (n + 1)/2 → Θ(n).

#Amortised analysis

Some operations are usually cheap but occasionally expensive. Amortised analysis averages the cost over a sequence of operations (no probability involved).

Example: vector::push_back doubles the capacity when full, copying all elements. A single push can cost O(n), but over n pushes the total copying is 1 + 2 + 4 + … + n < 2n, so each push costs O(1) amortised.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    long copies = 0;
    for (int i = 0; i < 1000; i++) {
        if (v.size() == v.capacity()) copies += v.size();     // a reallocation copies everything
        v.push_back(i);
    }
    cout << "1000 pushes, total elements copied: " << copies << " (less than 2 x 1000)" << endl;
    cout << "final capacity: " << v.capacity() << endl;
    return 0;
}

1000 pushes, total elements copied: 1023 (less than 2 x 1000)
final capacity: 1024

The three classic methods are the aggregate, accounting and potential methods.