> On Tue, 2017-09-05 at 15:05 -0700, Stefan Beller wrote:
>
> After having a sneak peak at the implementation
> it is O(1) in runtime for each added element, and the
> space complexity is O(well).
>
Incidentally I was reading about "complexity of algorithms" and there
was the following paragraph in the book,
Unfortunately, as Knuth observed, big-O notation is often used by careless
writers and
speakers as if it had the same meaning as big-Theta notation. Keep this in
mind when you see
big-O notation used. The recent trend has been to use big-Theta notation
whenever both upper
and lower bounds on the size of a function are needed.
So, if my interpretation is correct the above usage of O(1) and O(well)
should have been Θ(1) and Θ(well).
--
Kaartic
