Are there any theorems/formulas that apply to the height of comparison trees?

Question

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an array of N values, in Sedgewick's algorithms 4th ed. book for N = 3, the height of a comparison tree is 3.

He draws his comparison trees in such a way that all the internal nodes and the root represent the comparisons, for example (i:j) means compare a[i] to a[j], if a[i] < a[j] then the left subtree represents all the rest of the comparisons that we need to make, to finish the sort, and the leaves represent the permutations that we get after the sort. For example the left path for N = 4 is : (0:1), (1:2), (2:3), (0,1,2,3).

After I drew a tree for N = 4, the height was not 4, more specifically, an example would be the following path : (0:1),(1:2),(2:3), here a[2] > a[3] (3:1),(3:0),(3,0,1,2). So is there a formula?

In the example above we first find out that a[0] < a[1] < a[2] and then we find out that a[2] > a[3], so we need to compare a[3] to a[1] and a[0], so far the path length is 4, but then we add the leaf (3,0,1,2) and now the path length is 5.

Answer 1

Basically, we just need to look at the worst case comparison number, a worst case comparison number is when we compare 1 with 2...N, then 2 with 3...N, etc. that will take (N^2 - N)/2 steps (arithmetic progression ((N-1)*(N-1+1))/2). So that's the height of that tree.

So for N = 3 we get (3^3 - 3)/2 = (9 - 3)/2 = 3. For N = 4 we have (4^2 - 4)/2 = 6.