Big O

1. : TRUE
2. TRUE
3. FALSE
4. FALSE

Other Notation

• Big O is an upper bound notation ()
• Little O is a weak upper bound notation ()
• Big Omega notation is a lower bound notation ()
• Little Omega notation is a weak lower bound notation ()
• Big Theta notation if an exact bound notation ()

Examples

int fun3(int n) {
    assert(n > 0);
    for (int i = 0; i <= n; i++) {
        for (int j = i; j < n; j++) {
            printf("something");
        }
    }
}

Recursion

1. Identify the order of the function excluding any recursion
2. Determine the size of the data for the next recursive call(s)
3. Write the full recurrence relation
4. Look up the closed-form solution in the table (wow)

int fib(int num) {
    if (num <= 1) {
        return num;
    }

    return fib(num - 2) + fib(num - 1);
}

Amortized Constant Time

Doesn't matter if it's slow "every once in a while", as long as it's every once in a while.