Fors, and fors inside fors

Exercise 1.12

For each of the following fragments of code, analyze its cost.

Warning

You might be tempted to eye-ball the cost of some of the fragments below. This will very easily lead to errors.

Hint

To do this exercise you might want to look again at the sums in Exercise 1.1.

// Fragment 1
int s = 0;
for (int i = 0; i < n; ++i) {
    ++s; 
}

// Fragment 2 
int s = 0;
for (int i = 0; i < n; i += 2) { 
    ++s;
}

// Fragment 3
int s = 0;
for (int i = 0; i < n; ++i) { 
    ++s;
}
for (int j = 0; j < n; ++j) { 
    ++s;
}

// Fragment 4
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        ++s;
    }
}

// Fragment 5
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) { 
        ++s;
    }
}

// Fragment 6
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) { 
        ++s;
    }
}

// Fragment 7
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            ++s; 
        }
    }
}   

// Fragment 8
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        for (int k = 0; k < j; ++k) {
            ++s;
        }
    }
}

// Fragment 9
int s = 0;
for (int i = 1; i <= n; i *= 2) {
    ++s; 
}

// Fragment 10
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i*i; ++j) { 
        for (int k = 0; k < n; ++k) {
            ++s; 
        }
    }
}

// Fragment 11
int s = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i*i; ++j) { 
        if (j % i == 0) {
            for (int k = 0; k < n; ++k) { 
                ++s;
            }
        }
    }
}