insertion sort lower bound and why it compare to `1/(2^n)`?

Question

I have one question:

1. we know n!*(1/(2^n)) compared to 2^n, but what about insertion sort why it compare to 1/(2^n)?

I means why unlike the example for insertion sort reverse of 2^nwas used?

Answer 1

To use at most c(n) comparisons (with two possible outcomes) on an f(n) fraction of the inputs, we need f(n) n! ≤ 2^c(n). In the display formula they're using c(n) = n (which is a little too simple because they need to consider the asymptotic constant, but whatever) and f(n) = 1/2^n, yielding the desired formula n!/2^n ≤ 2^n <=> n! ≤ 4^n, which fails for large n.

Presumably the referenced part of the textbook goes over this, but f(n) n! is the number of inputs we need to distinguish, and 2^c(n) is the number of inputs we can distinguish with c(n) comparisons.