Loops – How to Prove a While Loop Calculates n^2

The complexity class is O(n²).

Visual explanation

Imagine a n·n square which lists all the values j takes on. We remove the diagonal (which has n entries) and the upper right half because j will never be larger or equal to i. We are then left with an area of (n² - n)/2.

 i  | values of j     | no of j values
----+-----------------+---------------
 0  | · · · · ·  ⋯  · |  0
 1  | 0 · · · ·  ⋯  · |  1
 2  | 0 1 · · ·  ⋯  · |  2
 3  | 0 1 2 · ·  ⋯  · |  3
 4  | 0 1 2 3 ·  ⋯  · |  4
 :  | : : : :    :  : |  :
n-1 | 0 1 2 3 ⋯ n-2 · | n-1
                       =====
                  SUM: (n² - n)/2

Mathematical explanation

The outer loop executes n times, the inner loop i times. We can write the number of executions of the inner loop body as ∑mi=1 i with m = n-1. The sum of all natural numbers up to including m can also be written as m·(m + 1)/2 (the formula for triangular numbers), which leads to n(n-1)/2.

Conclusion

Using either method, we can determine that the nested loops have a complexity of O((n² - n)/2) = O(n²).

I would write the if-statement slightly different, so it is taken when the input is successful.

for (;;) {
    cout << ": ";
    if (cin >> input)
        break;
    cin.clear();
    cin.ignore(512, '\n');
}

It's shorter as well.

Which suggests a shorter way that might be liked by your teacher:

cout << ": ";
while (!(cin >> input)) {
    cin.clear();
    cin.ignore(512, '\n');
    cout << ": ";
}