0
$\begingroup$

I am new to math and algorithms, I am trying to understand how does this equation: $|N| \le \sum\limits_{i = 1}^{h} 2^{i-1} $

Come to a conclusion of:

$|N| \le 2^h - 1$ and then

$h \ge log(|N|+1)$

This is the evaluation of a height of a binary tree and N is the total number of elements in a binary tree.

PS: I am new to math.stackexchange. Please recommend some better tags for this question.

  • 0
    Fixed it! Thanks!2012-07-07

2 Answers 2

1

We can see that the sum of a geometric progression: $\sum_{a\le k\lt b}{c^{k}}=\frac{c^{b}-c^{a}}{c-1}$, where $c\not=1$. Therefore, manipulating the range of the sum gives:

$\sum_{1\le k \lt h+1}{2^{k-1}}=\sum_{0\le k \lt h}{2^{k}}=\frac{2^{h}-1}{2-1}=2^{h}-1,$

Which is the answer you are looking for. In regards to the next part of your question, given:

$\left|N\right|\le2^{k}-1 \implies |N|+1\le2^{k}$

Taking $\log_{10}$ of both sides:

$\log_{10}{(|N|+1)} \le k\log_{10}{(2)}$

However, as $\log_{10}(2)\lt 1$:

$\log_{10}{(|N|+1)}\le k$

Which is the inequality you desired.


As mentioned by André Nicolas in his comments below, I shall explain a little more about the usage of the most common logarithms and the different notations regarding them.

In computer science, by far the most common form of logarithm is $\log_{2}$, usually written as $\lg$ or $\operatorname{lb}$ in CS literature. This form of logarithm is also known as the "Binary Logarithm" in some literature, and is the solution to the equation:

$2^{x}=a\implies x=\log_{2}{a}=\lg{a}=\operatorname{lb}{a}$

A simple example use of the binary logarithm is in determining the number of bits required to represent some integer, $n$, which we can find by evaluating:

$\left\lfloor\lg{n}\right\rfloor+1,$

Where $\left\lfloor x \right\rfloor$ is the greatest integer less than or equal to $x$.

The next most common logarithm in computer science is $\log_{10}$ also just written $\log$. This is also the most common form of logarithm in fields such as engineering, and is called the "Common Logarithm". These are solutions to equations of the form:

$10^{x}=a \implies x=\log_{10}{a}=\log{a}$

Finally, whilst not commonly used in computer science (but often used in other disciplines such as maths and physics), we have $\log_{e}$, usually written $\ln$, and called the "Natural Logarithm". This logarithm has properties of particular importance in maths, and you will see many examples of its use whilst browsing this site. It provides solutions to equations of the form:

$e^{x}=a\implies x=\log_{e}{a}=\ln{a}$

There are various rules which we can use to manipulate logarithms (above I have used the rule that $\log_{b}{a^{n}}=n\log_{b}{a}$, for all bases $b$), you can find many of these rules here and here.

  • 0
    I think it may be a good idea to mention the various possibilities for what could be meant by $\log$, since the OP may be very new to these things.2012-07-07
0

$|N|+1 \le 2^{h}$

$\log_{2}{(|N|+1)} \le h$

We use big O notation,

and get

$h \ge \log{(|N|+1)}$

  • 0
    I wonder where bigO is involved at all.2012-07-07