4 ms·
Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
by makeset 4y ago
Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.
- bee_rider 4y agoHey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.
- adwn 4y agoOnly for reasonably small stacks. Insertions at random indices won't stay O(1) when you're dealing with 100k pages and more – i.e., when you can't pick them up in one movement.
- bee_rider 4y agoI guess such a stack would fall over quickly, resulting in a heap. But again not the programming one.
- adrianmonk 4y agoIronically, the answer isn't a stack.