1
$\begingroup$

I think some of the log properties are flying over my head but I'm trying to understand how the depth of mergesort is...

$1 + \log_2 n$

I understand that to get the depth, you would have to divide $n$ by $2^x$ but I don't how this leads to the above.

It's probably some simple log principal but I'm not sure.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The merge sort algorithm creates a complete binary tree, which has depth 'd' and at each level, a total of n elements. So, 2d ≈ n, which implies d ≈ log2 n

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hi. I'm coming back to this as I still have doubts. I understand the text your wrote out but I'm not sure why it's +1 as well $\endgroup$
    – pad11
    Commented Oct 1, 2016 at 16:39
  • $\begingroup$ @pad11 If you keep dividing n by 2, you'll eventually get to 1. Namely, it takes log2(n) divisions by 2 to make this happen, by definition of the logarithm.Every time we divide by 2, we add a new level to the recursion tree. Add that to the root level (which didn't require any divisions), and we have log2(n) + 1 levels total. $\endgroup$
    – Anjo
    Commented Oct 1, 2016 at 17:19
  • $\begingroup$ Got it thanks! Thanks for following up $\endgroup$
    – pad11
    Commented Oct 2, 2016 at 12:20
0
$\begingroup$

I will assume that by depth, you mean the number of levels of partitioning (splitting the components into two parts) that merge sort performs.

If this is the case, the algorithm for finding the depth should not be "log2(n) + 1", but rather the ceiling of "log2(n)" (the ceiling function rounds numbers up to the nearest whole number).

This is because there are two types of inputs you can start with:

  1. When "n" is a power of 2.
  2. When "n" is not a power of 2.

In the first case, you can keep partitioning the input into components until you reach components of size 1. At this stage there can be no more partitioning and the number of levels of partitioning is a whole number. Thus the answer is not affected by the ceiling function.

In the second case, you can partition the input into components however you will arrive at a stage when some inputs have components of size 2 as well as components of size 1. This is represented in the logarithm by the decimal numbers when you calculate "log2(n)". Obviously you cannot take a fraction of a step, so the ceiling function rounds it up to the next whole number.

TLDR: "ceiling(log2(n))" instead of "log2(n) + 1"

Note that in this answer I do not consider the root level as a level of partitioning. If I did wish to, I would simply "+1" to the ceiling.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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