3 ms·
Computing a sorted list online is an amortized O(1) operation, O(log n) worst case.
by AstralStorm 4y ago
Computing a sorted list online is an amortized O(1) operation, O(log n) worst case.
- ironSkillet 4y agoAdding elements one at a time is O(log n) into an already sorted list. But producing a complete sorted list requires doing that n times, so you end up with n log n anyways. Am I missing something?