I think you are mixing runtime scalability with the actual complexity. Big-O definition from Wikipedia: Let f(x) and g(x) be two functions defined on some subse

I think you are mixing runtime scalability with the actual complexity. Big-O definition from Wikipedia: Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes f(x) = O(g(x)) as x -> infinity if and only if, for sufficiently large values of x, f(x) is at most a constant times g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that |f(x)| <= M|g(x)| for all x > x0. In the above case M = 32, f = mergesort and g(x) = x because no matter of large input you have mergesort will always take less than or equal to 32n operations (since log(n)<=32) .