Big O notation

[sporx]

how do you figure out the Big O notation order of magnitude for something? for example, whats the order of magnitude for each fundamental operation performed on arrays?

[imi]

Usually, a simple array access is defined of magnitude O(1) - like all other direct access to variables. At least if you calculate the O-notation for a Random Access Memory-Machine (it is different for plain turing machines, but these are usually of no interest when it comes to O-complexity).

You calculate the complexity of a function, by going through the source and count the individual's together. Howver, remember, that "O(x) + O(y) = O(max(x,y))" and "O(x)*O(y) = O(x*y)". Cascaded loops are always multiplying. Sequences of instructions are added (hence the maximum is used for sequences)

For example:

void count_lines(char* str, int size)
{
    int i; // no complexity. It's only a declaration
    int c = 0; // simple variable access -> O(1)
    for (i = 0; i < size; ++i) // loop executed size times -> O(size)
        if (str[i] == '\n')  // array access -> O(1)
            c++;  // simple Variable access -> O(1)
    return c; // simple variable access -> O(1)
}

So in the end we get O(1) for line 4 which is in sequence to the loop and the return in line 8.
The loop is cascading, so you have to multiply. The inner part of the loop in line 6 and 7 are a sequence again, so it's O(max(1,1)) = O(1). Cascading is multiply, so the whole loop is O(size)*O(1) = O(size*1) = O(size).

So for the whole function, you get: O( max(1, size, 1) ) = O(size).

Ciao, Imi.

[jsmith]

See also

http://www.cplusplus.com/forum/beginner/15528/