Big-O notation: Which algorithm performs better?

Suppose (ideally… again, ideally) that you have created different algorithms to solve a particular problem. Now, suppose that you have determined the order for those algorithms using Big-O notation. Which algorithm performs better? 

This ABC goes like this:

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!) < O(N^N)

Constant running time is the best… then logarithmic, linear, linearithmic, quadratic, exponential, factorial and I leave the name of the last one to you :-)

Having constant, logarithmic and linear algorithms should be you goal, although this might be difficult to achieve. In real world problems, if your solution algorithm is higher than quadratic, I would advise you to drop it…

I have seen lots of people get frozen with a simple question: which function grows faster? Remember the correlation above…it’s easy.
Notice: Having a O(1) ,O(log N) or O(N) algorithm doesn’t guarantee that your code is well written or optimized. Even with those orders there might be place for improvements and refactoring.

No comments:

Post a Comment