Developers do not understand big Oh

Computer scientist should really start paying more attention to their algorithm professors at university. After reading this post in the gnome rss I found it ridiculous/amazing that a developer had to write code to actually prove a well know proven behavior in searching algorithms. That post first proves that a lot of developers always to try solve their problems with the same hammer (binary search) and that really do not understand Big Oh. Here is the explanation I gave in my comment in the blog:

Comment

Did you really have to write the code?!? Common that is what big Oh notation is for. There main problem people are having is to truly understand what big Oh means. What I mean is the following, we know as a fact that a linear search is O(n) while a binary search is O(log N), of course if we do not understand our algorithm (in this case binary search) we will think that O(log N) will always outperform O(N) but that is not true.

If you carefully think about the definition of big Oh notation you will find that in most cases we are worried about N begin close to a large number. This is a very important fact, because we are ignoring the exact and precise performance of our implementation. If we where to talk about the performance of the binary search we will have to say that it is O(log N) + K where K represents the constant overhead that our algorithm has. Getting back to big numbers, if we say that K is constant, it means that when the limit of N is infinite K becomes 0 since a small number divided by a large number is nearly 0. At this point we can agree that if our problem is facing large numbers, we ought to ignore K since it has no added value. Nevertheless, there are cases where O(N) does outperform O(log N) because we are working with a small number of items. In the linear search algorithm you have not overhead (nearly) meaning that K is 0 while in the binary search we do have K, because the number of items is small, we cannot ignore K! That is, O(N) is better than O(log N) + K because K is large enough when dealing with a small list!!

As you can see, if the algorithm is correctly understood as well as the environment in which we use it, there is actually no need to write tests cases etc… you could have reached the conclusion using pen and paper .

Nevertheless, I think this is a goo post for other people but please explain somewhere that the theory s right! people should stop using big Oh until the really understand it meaning and the algorithm implementation…