basic code runtime analysis examples

// O(1) since it does not vary with n
void foo1(int n) {
    // `c` is global constant
    for (int i ; i <= c; i++) {
        cout << "hello\n";
    }
}
 
// O(n), linear w.r.t. n, prints hello n/c times
void foo2(int n) {
    // `c` is global constant
    for (int i = 1; i <= n; i += c) {
        cout << "hello\n";
    }
}
 
// O(n^2)
void foo3(int n) {
    // `c` is global constant
    for (int i = 1; i <= n; i += c) {
        for (int j = 1; j <= n; i += c) {
            cout << "hello\n";
        }
    }
}
 
// O(n^2)
void foo2(int n) {
    // `c` is quadratically related to n
    for (int i = 1; i <= c; i++) {
        cout << "hello\n";
    }
}

For nested loop that initializes its counter using the outer loop’s counter like the one below, the inner loop still has $O(n)$, since half of inner loop iterations deals with at least $\frac{n}{2}$ elements.

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // O(1) work here
    }
}