Lower bounds

A lower bound says every algorithm in a class must do at least this much work in the worst case. Comparison sorting: each comparison has two outcomes, so k comparisons distinguish at most 2ᵏ orders. There are n! orders, so k is Ω(n log n).

Factorials vs powers of two

def fact(n):
    p = 1
    for i in range(2, n + 1):
        p *= i
    return p

def log2(n):
    k = 0
    x = n
    while x > 1:
        x //= 2
        k += 1
    return k

for n in (3, 4, 5, 6):
    print(n, "n!", fact(n), "2^(n log n)", 2 ** (n * log2(n)))

2^(n log n) grows at least as fast as n! in this table’s spirit: you need on the order of n log n yes/no questions.

What this does not say

print("counting sort of tiny ints is not a comparison sort")
print("bucket of 0/1 flags:", [0, 1, 0, 1, 1].count(0), "zeros")

If you may use the numeric value as an index (counting sort), you leave the comparison model. Then Ω(n log n) need not apply.