2 ms·
Decreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(
by csjh 2y ago
Decreasing capacity wouldn't affect the theoretical complexity of algorithms using it - same concept as increasing capacity during push still being amortized O(1)
- _flux 2y agoI don't think it works that way when a container can grow and shrink, because an algorithm can trigger those operations any number of times, not just O(log(n)) times.
- csjh 2y agoI'm not sure where you're getting O(logn) from here. If it couldn't work that way when a container can grow and shrink, then arrays wouldn't be able to have both amortized O(1) push and pop as they do in most relevant implementations. As long as the expensive O(n) resize operation happens at some frequency relative to the size of the container rather than every constant size difference (i.e. capacity doubles when length == capacity and halves when length == capacity/2) then it will amortize out to O(1). There's a proof available in section 2.1.2 of this textbook: https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_Stack_O.html https://opendatastructures.org/ods-java/2_1_ArrayStack_Fast_...