0
$\begingroup$

I generally visualize $\log_{2}$ of a number as an inverted binary tree, for example to know how many times 8 needs to be divided to become one I image a inverted tree of 8 leaves then, the level before that with 4 leaves until the root node, if we count the number of edges we get the correct answer in this case 3.

For nodes with power of two works fine but the process blurs when the node count is not power of two. I am not able to visualize how that process would proceed. Since, I am a visual leaner therefore I feel comfortable when I have some visual clue to follow.

I came across this thinking while reading an algorithm book where it was told that:

Since mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be $\lceil\log_{2}{n}\rceil$

I need to know some intuitive explanation or where I am going wrong? Also, I always get confused when to take ceil or floor.

$\endgroup$
1
$\begingroup$

If the number $n$ satisfies $2^{k-1}<n<2^{k}$, this means that $k-1$ steps cannot be sufficient because with $k-1$ steps we can only sort $2^{k-1}$ elements.

But you can fill up the $n$ entries with $2^{k}-n$ entries greater than every element of the list to get $2^{k}$ elements.

"mergesort" can sort this extended array in $k$ steps. Then, we have also sorted the $n$ elements. So, we need $k$ steps if $2^{k-1}<n<2^{k}$.

This means $(k-1) log(2)<log(n)<k\ log(2)$ , implying $$k-1<log_2(n)<k$$

The expression you mentioned is $k$ in this case, and this is the number of steps we need.

$\endgroup$
  • $\begingroup$ I am still confused, your first element makes sense but after that can you be please more clear? Also, what about the ceil function? $\endgroup$ – CodeYogi Mar 16 '16 at 2:12
  • $\begingroup$ For example 7 is greater than 4 but less than 8 and since we are talking of worse case we would go for $\log_{2}8$, right? $\endgroup$ – CodeYogi Mar 16 '16 at 15:06
  • $\begingroup$ Yes, exactly that. $\endgroup$ – Peter Mar 16 '16 at 18:23

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.