News for hackers. Stuff that matters.

A comment on The time complexity of the libc++ deque push_front implementation is O(log n). Parent comment

Re:The time complexity of the libc++ deque push_front implem... by mgaunard on Sunday November 28, 2021 @06:21PM (#29374305)
Amortized O(1) does not satisfy the specified requirements.
[ Parent | on HN ]
Re:The time complexity of the libc++ deque push_front implem... by monocasa on Sunday November 28, 2021 @06:52PM (#29374578)
Oh, ok, it used to be amortized constant O(1), but changed at some point apparently.

https://web.archive.org/web/20150310134852/https://en.cppref...

[ Parent | on HN ]
Re:The time complexity of the libc++ deque push_front implem... by mgaunard on Monday November 29, 2021 @04:00AM (#29377695)
That's an error that this website did. It's not an authoritative source.

It's always been non-amortized since 1998.

[ Parent | on HN ]