Algorithm Speed Order of

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.

Upvotes: 6

Answers (8)

David Santamaria

Reputation: 8801

I am not a big fan of answering my own questions, but I found this today and remind me this SO question.

http://bigocheatsheet.com/

Upvotes: 0

Larry Watanabe

Reputation: 10184

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.

Upvotes: 1

Antti Huima

Reputation: 25512

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!

Upvotes: 1

Bill the Lizard

Reputation: 405675

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. :)

Upvotes: 4

Chris Upchurch

Reputation: 15517

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

Upvotes: 1

sirprize

Reputation: 426

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.

Upvotes: 1