Algorithm Speed Order of

Question

Sometimes I get totally fooled trying to estimate an algorithm's speed with the O(x) notation, I mean, I can really point out when the order is O(n) or O(mxn), but for those that are O(lg(n)) or O(C(power n)) I think that I am missing something there... So, what are your tips and tricks for an easy estimate with a fast overlook on an algorithm?

As an example of what I am looking for, here are some for the easy ones (can be wrong, but trying my best):

• O(n): If there is a simple loop from 1 to n (or several of them, but not nested.
• O(mxn): A nested loop inside of another where the limits are m and n.

Thanks in advance.

Answer 1

Recursive, divide-and-conquer algorithms are often O(logN). An algorithm that loops over a divide-and-conquer would be O(NlogN).

Answer 2

Here's a blog post that might help:

The cost of breaking things down and putting them back together

That post explains the "master theorem" for working with big-O orders.