linsort - 8
Lin / Devi
From previous discussion, suffices to determine the height of a decision tree.
h – height, l – no. of reachable leaves in a decision tree.
In a decision tree for n elements, l n!.
In a binary tree of height h, no. of leaves l 2h.
Hence, n! l 2h.
Any comparison sort algorithm requires (n lg n) comparisons in the worst case.