Proof

• „Given a list of n elements, the minimum amount of steps a computer needs to sort it is O(n log n).“

• every sorting algorithm has to collect information about its input (i.e. by doing comparisons)

• this knowledge can be summarized in a decision tree

• this approach ignores algorithm-specific details such as data movement and structures