|
|
|
|
|
|
by budabudimir
2795 days ago
|
|
|
That's true for array, that expected insert time is O(1), and it still holds for N inserts, because you double the size every time, which yields O(2N) time complexity. This is not the case for this data structure, time complexity of inserting N elements is O( N log N ), therefore expected complexity of inserting single element cannot be O(1), even if single insert sometimes can be O(1), O(1) in the paper referred to restructuring, after O( log n ) search time. We could be violently agreeing, not sure :) |
|
|