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.

enter image description here


Two reasons:

  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.

  2. If the goal is to prove an upper bound on an algorithm's runtime, then rounding down would be unsound, but rounding up is acceptable.

  • $\begingroup$ Thank you. Can you please rephrase "(because we want to be certain that the exact number of steps is less than the function of n we produce)"? Since it's an upper bound, should it be larger than number of steps function produce? $\endgroup$
    – Avra
    Feb 18 at 3:59
  • 1
    $\begingroup$ Ah yeah, I meant that the actual number of steps must be less than our estimate, because we're trying to show that the number of steps is "small". I'll rephrase to clarify. $\endgroup$
    – Karl
    Feb 18 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.