O() notation

[WingedPanther]

Saying a function is O(6x^2) and saying it is O(x^2) is saying the same thing. The constant multiplier is made irrelevant by the definition of O().

[TcM]

Yeah I understood that but now, what is the use of this?

[WingedPanther]

O() gives you a measure of algorithmic efficiency. If you have an algorithm that is O(x), it is fundamentally more efficient than O(x^2). The actual values for the algorithms may be 1000x+1000 vs x^2, but after a while, the x^2 version still becomes worse. Algorithms are usually measured in efficiency against memory usage or speed. They are also sometimes rated against average and worst-case efficiency (quicksort has different values).

If you analyze the efficiency of your code, it will generally help you determine where to start making changes and what can be left alone.

[TcM]

Ok, I kinda understood that, but is there a program that calculates this, or what? I mean the for example O(x) should give some sort of answer that will help you.... or it's just like that, no answers and no working?

[WingedPanther]

As an example:
The algorithms for various containers/algorithms in the C++ STL have efficiencies as part of the standard. So, for instance, copying a deque is supposed to have linear ( O(x) ) efficiency. (kinda makes sense that it should take about as long as it has elements to copy, right?)

Unfortunately, the analysis of whether a given implementation meets the a given efficiency is a bit... complicated. I read over the efficiency calculations for quicksort and heapsort a while back, and didn't fully understand them after a casual reading. A good book on data structures/algorithms will spend a LOT of time discussing how to calculate O() for a given algorithm.

[TcM]

Hmm, ok, I thought that it could be complicated.

Thanks for your help.