Calculating time complexity and space complexity

[chrisname]

How do you calculate the time complexity of an algorithm (in "Big-O" notation)? I read something on the Internet just now that said to count the number of operations; so, I wrote a very quick bubblesort implementation and counted. I got n²+15 (this is counting things like comparisons, declarations, assignments, etc.).

I tried to find a good article about it but couldn't. Could someone explain to me, or else point me to a good explanation?

Thanks.

[Albatross]

Manipulate your variables, determine a best and worst case scenario, use those, plot a few graphs vs time, see what those graphs resemble. At least, that's what I do.

-Albatross

[moorecm]

I'm by no means an expert on algorithms but I just look at the number of iterations... The easiest ones to spot are for loops. Here are some examples:

{
    /* something that executes once is done in O(1) or constant time */
}

for( int n = 0; n < 10; ++n ) // note that as n increases, the number of iterations increases
                              // at a fixed rate
{
    /* something that executes n times is done in O(n) or linear time */
}

for( int n = 0; n < 10; ++n )
{
    for( int n = 0; n < 10; ++n )
    {
        /* something that executes n*n times is done in O(n2) or quadratic time */
    }
}

The following is also quadratic time, just like a quadratic expression in algebra. The largest term is the one that counts, Big-O notation usually drops the lesser terms, so O(n²+n) would just be called O(n²).

for( int n = 0; n < 10; ++n )
{
    for( int n = 0; n < 10; ++n )
    {
        /* something that executes n*n times is done in O(n2) or quadratic time */
    }
}
for( int n = 0; n < 10; ++n )
{
    /* something that executes n times is done in O(n) or linear time */
}

Binary searches are O(log n) or logarithmic time. Etc.

See:
http://en.wikipedia.org/wiki/Big_O_notation

[chrisname]

Oh, thanks! I get it now; that's why I got O(n^2 + 15) for bubblesort... Thanks. That's not that complicated, actually.

What about space complexity? I guess it's pretty similar.

[moorecm]

What about space complexity?

I don't know but let me know what you find out!

[jsmith]

Computing space complexity is the same.

[chrisname]

Oh; so if an algorithm has an O(n) time complexity, the space complexity is also O(n)?

[jsmith]

No, I meant you compute the space complexity using the same technique as for time.

[chrisname]

So, the space complexity of this code:

void pointless(const char* str, size_t n)
{
        char tmp[n];

        strncpy(tmp, str, n);
}

would be O(2n)?

[jsmith]

It would be O(n) since the function uses only n bytes. The n bytes used by
the source string wouldn't be counted.

Setting that aside, O(kN) where k is a constant is equal to O(N) (the constant is dropped).

[chrisname]

Ok. Thanks, moorecm, jsmith; I understand this now. Thanks alot.