News for hackers. Stuff that matters.
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.
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.