People reading this write-up should keep in mind that the author uses the term &quot;complexity class&quot; incorrectly. When the author says this, they actually mean &quot;worst case runtime&quot;. It never dives into space complexity, which is yet another complexity measure for evaluating the performance of these operations. In some spots they completely abuse big O notation to make it do things it is not supposed to. For example:<p>&quot;O(==) is the complexity class for checking whether two values in the list are ==&quot;<p>This stuff needs to be fixed since it is only going to lead to later confusion (and embarrassment).<p>A complexity class is a set of problems that tend to be similar in resource requirements. O(f(n)), more or less, means asymptotically bounded from above by c*f(n) for some constant, c, as n -&gt; inf. It is a general way to represent the asymptotic growth rate of functions and is NOT married to the concept of complexity classes.