alt Hacker NewsThere are a lot of misconceptions and things being confused together in your post. For one complexity classes are related to decision problems, not algorithms. An algorithm does not have a complexity class, rather it's decision problems that belong to a complexity class. 3SAT is a decision problem that belongs to the NP-complete complexity class regardless of any particular algorithm that implements a solution to it.
Secondly, it's a common misconception that O(f(n)) refers to worst case complexity. O(f(n)) is an upper bound on the asymptotic growth of f(n). This upper bound can be used to measure best case complexity, worst case complexity, average case complexity, or many other circumstances. An upper bound does not mean worst case.
For example I often perform code reviews where I will point out that a certain operation is implemented with the best case scenario having O(log(N)), but that an alternative implementation has a best case scenario of O(1) and consequently I will request an update.
I expect my engineers to know what this means without mixing up O(N) with worst-case scenarios, in particular I do not expect an improvement to the algorithm in the worst case scenario but that there exists a fast/happy path scenario that can avoid doing a lot of work.
Consequently the opposite can also happen, an operation might be implemented where the worst case scenario is o(N), note the use of little-o rather than big-o, and I will request a lower bound on the worst case scenario.
> An algorithm does not have a complexity class, rather it's decision problems that belong to a complexity class. 3SAT is a decision problem that belongs to the NP-complete complexity class regardless of any particular algorithm that implements a solution to it.
Both algorithms and problems have their own complexity. The complexity of an algorithm is the time it takes that algorithm to finish. For example, quicksort is an algorithm, and its average case complexity is in O(n log n). I called O(n log n) a complexity class, this was indeed sloppy on my part - I was just trying to find a name for this set.
> Secondly, it's a common misconception that O(f(n)) refers to worst case complexity.
I know, and my post was very explicitly avoiding this misconception. I explicitly gave the example that the average case complexity of quicksort is in O(n log n).
> Consequently the opposite can also happen, an operation might be implemented where the worst case scenario is o(N), note the use of little-o rather than big-o, and I will request a lower bound on the worst case scenario.
I'm not sure what you're trying to say in this part. o(n) is basically the set of all sublinear functions, e.g. log(n), but also 1. Any function in o(n) is also in O(n), though the converse doesn't hold. So, if you know an algorithm has worse complexity in o(n), you know more information about the algorithm than if I tell you it has worse case complexity in O(n). Knowing a lower bound is still useful in either case, of course, since a constant time algorithm and a logarithmic time algorithm are still both in both sets.