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:
1 2 3 4 5 6 7 8 9
|
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.