Big O Notation

Big O represents the running time as a function of the size of the input (N).

We simplify to just the highest order term, and ignore constant coefficients of N.

Examples:

$$O(N), O(N^2), O(N log(N)), O(1)$$

Formal definition:

$$\begin{array}{c}{f(n)=O(g(n))} \\ {\text { iff } \exists \text { constants } c \text { and } n} \\ {\text { such that } \forall n>n_{0}} \\ {f(n) \leq c g(n)}\end{array}$$

Basically: f(n) worst case is g(n), so f(n) will be the same or faster than g(n).

Comparison of some common running times.

An example:

int max(int items[], int size) { // Running time is O(N)
    int largest = items[0];
    for(inti=0; i<size; i++)
        if (items[i] > largest) 
            largest = items[i]; 
    return largest;
}