# Solving recurrence of Merge Sort

Discussion in 'Homework Help' started by zulfi100, Jan 3, 2016.

1. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
I cant understand why we get log n while solving recurrence of Merge Sort. I have attached the book content. It replaces the ' 1 ' on RHS by log n. It says" because all of the other terms cancel & there are log n equations and so all the 1s at the end of these equations add up to log n."

If n is 8, then we would split list into 4, 2 and 1. This means that there would be 3 equations, but log 8 is not 3 mathematically.

Can some body please explain me the number of equations for n=8?

Zulfi.

2. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
The base that applies here is base 2. The base-2 logarithm of 8 is 3.

3. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
Thanks for your answer. In my calculator, i have log key (which 10 to the power x written on its top) and ln key (which has e raised to the power x written on its top). How can we calculate base-2 logarithm using calculator?

Zulfi.

4. ### djsfantasi AAC Fanatic!

Apr 11, 2010
2,911
881
Divide $log_{10}(number)$ by $log_{10}(2)$

5. ### WBahn Moderator

Mar 31, 2012
18,089
4,917
The best way is by understanding what a logarithm is -- if you do that, then you can quickly derive how to calculate the log to an arbitrary base in just a couple lines of algebra.

A logarithm, by definition, is the exponent that a base must be raised to in order to equal a number. So we know that

$
1000 \; = \; 10^3
$

So, by definition, 3 is the base 10 logarithm of 1000.

If we want the base B logarithm of a some number x, then we are looking for the value y such that

$
x \; = \; B^y
$

So we simply solve this for y by taking the logarithm of both sides:

$
\ln(x) \; = \; y \, \ln(B)
\,
y \; = \; \frac{\ln(x)}{\ln(B)}
$

Note that it does not matter which base you take the logarithm with respect to -- as long as you use the same base for both operations.

So for the base-2 logarithm, you simply have

$
y \; = \; \frac{\ln(x)}{\ln(2)} \; = \; \frac{\log_{10}(x)}{\log_{10}(2)}
$

6. ### zulfi100 Thread Starter Member

Jun 7, 2012
320
0
Hi,
Thanks for this thorough answer.

Zulfi.