Re:What skills do self-taught programmers commonly lack?
by fhars on Tuesday April 05, 2011 @03:28AM
(#2410057)
But "amortized" is irrelevant in the context of quicksort, as it is not an amortized algorithm. You may hit an unlucky streak and get the worst case of O(n^2) behaviour on every call. An amortized algorithm on the other had would guarantee that while each individual operation on a data structure may hit the worst case, it will always (and not just in the average case) average out over many operations on the same data structure.
[ Parent
| on HN ]
Re:What skills do self-taught programmers commonly lack?
by strlen on Tuesday April 05, 2011 @04:06AM
(#2410124)
Doh, screw up on my part. You are completely right. An amortized algorithm would be something like a dynamic array (std::vector or ArrayList) in this case, which is doubled every time it hits capacity.