O(1) is usually prefixed with "amortized" or "average worst-case", which is where the difference in interpretation comes from imo. I found this explanation a bi

O(1) is usually prefixed with "amortized" or "average worst-case", which is where the difference in interpretation comes from imo. I found this explanation a bit wishy washy on some details but good (and has an appropriate appeal to authority/original sources). https://m.reddit.com/r/compsci/comments/2z74z8/why_is_hashtable_lookup_o1_rather_than_olog_n_or/ https://m.reddit.com/r/compsci/comments/2z74z8/why_is_hashta...