# Number of Comparisons Binary Insertion Sort and the Ceiling Function

I found that the number of comparisons for binary insertion sort is:

First Pass: 1 comparison as we compare the first two elements.
Second Pass: 2 comparisonss as we compare the third elements with the first two elements.
$$k^{th}$$ Pass: $$\left\lceil\log_2(n)\right\rceil$$ comparisonss.

Question: Why the ceil function was used here instead of the floor function? I saw this is the case for a lot log-based algorithms, where the ceiling function is used to estimate operation numbers instead of floor functions.

1. $$\lceil \log_2 n\rceil$$ is the correct exact count, assuming that with $$k$$ comparisons you can binary search an array of size at most $$2^k$$. For example, $$\log_25$$ is between 2 and 3, but with 2 comparisons we can only binary search an array of size $$2^2=4$$, so we need $$\lceil \log_25\rceil=3$$ comparisons to binary search a 5-element array.