3 ms·
It's possible to implement a 64 item stack so you can call it O(1) and in-place. But that's such an effort in futility that I refuse to do so. So it's theoreti
by scandum 4y ago
It's possible to implement a 64 item stack so you can call it O(1) and in-place.
But that's such an effort in futility that I refuse to do so. So it's theoretically and practically in-place, but not technically.
- def-lkb 4y agoOf course, this is nitpicking :). For all practical purpose, this O(log n) is O(1). If you are interested, I can try to recover the proof that the rotation step can be done in O(n), thus allowing to apply the master theorem on the main recursion and getting the O(n log n) result.
- scandum 4y agoI'm not that interested as I'd prefer to count each move and prove it that way, but perhaps Peter (orlp) is interested?