Re: O() notation
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.
|