PROBLEM:  How do we characterize how "fast" (or "slow") an algorithm is,...
    INDEPENDENT OF COMPUTER SPEED or speed of an individual operation?
    (... so that we can compare it to another algorithm)

We only care about large inputs.

Big-O is a notation for describing the type of "growth" of a function.
 - Is it linear?
 - Is it quadratic?
 - Is it _______?

f(n) is O(g(n)) if there exist constants c and k, such that f(n) ≤ cg(n) for n ≥ k.

Beyond a certain point (k), f(n) will be less than some constant factor times g(n).

2w + 1 is O(w) .... c=3  k=2
2w² + 3w + 1 is O(w²) .... c=5  w≥10

O(…) is a time complexity (expression)
"    is a time bound
"    is an asymptotic complexity


SLOW ALGORITHM (for sufficiently large n)
    n^n
    2^n ....... "exponential"
    n⁴
    n³
    n² ........ "quadratic time"
    n ......... "linear"
    log(n) .... "logarithmic"
    1 ......... "constant time"
FAST ALGORITHM

If your algorithm is like this:
    for(int i = 0; i < n; i++) {
    }
... it is O(n) ... or "linear"

If your algorithm is like this:
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
        }
    }
... it is O(n²) ... or "quadratic"

If your algorithm is like this:
    for(int i = n; i >= 1; i /= 2) {
    }
... it is O(log(n)) ... or "logarithmic"

PRACTICAL TAKEAWAY

Structure matters more than the constant number of steps inside your loop.

Doing something 2 or 3 (or constant number) of times is better than nested loops.

for(int i = 0; i < n; i++) {
}
for(int i = 0; i < n; i++) {
}
for(int i = 0; i < n; i++) {
}

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
    }
}