Algorithm Speed Order of

Question

Hi folks,

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

O(lg(n)): If your problem gets smaller by some proportion of n (often n/2) at each step of your algorithm and each step does a constant amount of work. Binary search is a good example since each step cuts your problem size in half by doing a constant amount of work (calculate the mid-point and do one comparison).

Note that the n is on the top of that proportion. This is not the same as your problem size reducing by 1/n at each step. :)

Answer 3

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.

Answer 4

If you're looking for a quick way to estimate the runtime of an algorithm, the other answers are good. If you want a more elaborate answer, I suggest you look at the "Master theorem". In the German article, there is a nice table to that.

Edit: John D. Cook has made a nice recap to the master theorem, see the Link his answer.

Answer 5

The Wikipedia article on Big O Notation has a nice chart of the orders of common functions.

Answer 6

Hi, the asymptotic complexity of algorithms is important in practice, and here are some of rules of thumb I use when I review mine or other people's code. Usually practical computer algorithms are functions of many variables and nontrivial data structures, but let us assume (just for illustration) that our algorithm f takes basically a single integer X as its argument, and we want to find the asymptotic complexity of f in terms of X. Suppose f(0) is trivial. Then in general:

• Every nested loop from 0 to X adds an exponent to X, so two loops (one nested inside another) gives X**2 (quadratic).
• If f(X) calls f(X-1) tail-recursively, it corresponds usually to iteration, i.e. a single outer loop (O(X)).
• I have seen routines which the author intended as iterative, but where there is both iteration from 0..X AND a tail-recursion to X-1; these result in quadratic behavior (O(X**2))
• If f(X) calls f(X-1) twice or more, it results in an exponential algorithm, and you get O(2**X) from that.
• If f(X) calls f(X/2) twice, it corresponds complexity-wise to single iteration (it is a divide-and-conquer algorithm). (It results in O(X log X) or O(X) depending on the details but I realize that I think of it as a single iteration anyway.)
• If f uses any ordered data structure (ordered set, priority heap etc.) that has been properly implemented, and the algorithm adds roughly X objects to the data structure, the operations are O(log X). So if a constant number of data structure operations take place in a loop, say, you get O(X * log X).
• If the ordered data structure is improperly implemented, you could get O(X) instead of O(log X) for the individual operations.

Some special cases:

• Algorithms which grow strings or memory areas by appending to them, do in many languages incur O(X**2) overhead, such as

  for (i = 0; i < X; i++) { s += "foo"; } // quadratic
  

• This typical nested loop has also X**2 overhead:

  for (i = 0; i < X; i++) { for (j = 0; j < i; j++) { ... } } // quadratic
  

• C++ STL containers like std::set and std::map have O(log X) overheads for almost all operations

• strlen(s) and other similar counting algorithms when they return X have O(X) overheads
• memcpy etc. result in O(X)
• There are complexity-wise dangerous operations, such as erasing an element by equality comparison from a linked list, which yield O(X) or worse
• When using template-based containers, make sure that the comparison, ordering etc. operators are fast and do not have hidden complexity factors
• If you use reference counting, the dropping of a reference can be worst-case O(X) operation if you drop the last reference to a linked list of references whose length is X
• Copying complex data structures in object-oriented languages can yield strange asymptotic complexities if the routines to copy objects are nontrivial and e.g. update global object sets

Just my 2 cents! Hope this helps!

Answer 7

Usually something like O(logN) comes about because the data is size N, but it is organized e.g. in a tree where the depth of the tree is logN. If the typical search involves going from the root to the leaf (in worse case) then it is easy to see that the algorithm will be O(logN).

There are no hard and fast rules - you just have to look at each case, figure out the worse case scenario, and calculate what the cost of that would be.