The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is
The tightest upper bound on the number of comparisons, in the worst case, for comparison-based sorting is
The tightest lower bound on the number of comparisons, in the best case, for comparison-based sorting is
The tightest upper bound on the number of comparisons, in the best case, for comparison-based sorting is