Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You probably mean $2^{i-1}$ instead of $2^h-1$. –  Did Jul 7 '12 at 10:03
    
Fixed it! Thanks! –  John Jul 7 '12 at 10:11

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
In a CS setting, it is unlikely that by $\log$ they mean $\log_{10}$. –  André Nicolas Jul 7 '12 at 11:37
    
@AndréNicolas true, but $\lg$ will follow trivially in a similar way. Should I include it in my answer anyway? –  Shaktal Jul 7 '12 at 11:38
    
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. –  André Nicolas Jul 7 '12 at 11:48

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

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

We use big O notation,

and get

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

share|improve this answer
    
thanks alot for your answer, i have updated my question a little! I am also curious about how does it get $2^h-1$ –  John Jul 7 '12 at 10:23
    
@John It's Geometric progression –  hbc Jul 7 '12 at 11:30
    
I wonder where bigO is involved at all. –  Did Jul 7 '12 at 13:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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