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.

Let's say I have example of phonebook lookup. I need to find one record in it. I can always divide phonebook into 2 equal parts and try to find a record in that way.

3 names - 2 times
7 names - 3 times
15 names - 4 times 
1000000 names - 20 times

For big O notation it says this algorithm takes $O(\log n)$ comparisons.

Why they made such conclusion? I even can't find which logarithm I should use to create such sequence.

share|improve this question
1  
Any two logarithms are related by a constant, that is, $\log_an = \frac{\log_bn}{\log_ba}$, which dilutes in the $O(\cdot)$ notation, so it doesn't matter which logarithm you use. –  dtldarek Jan 31 '13 at 21:59
    
As an aside, this is why the "twenty questions" game is feasible. Twenty questions, properly formed, can uniquely distinguish among a million possible answers. –  Rick Decker Feb 1 '13 at 1:35

4 Answers 4

Notice that $$ \log_a n = \frac{\log_b n}{\log_b a} = O(\log_b n) $$ so it does not matter which logarithm you choose.

To compute the actual number of steps, notice that the number of steps is $n$ if the numbers are in between $2^{n-1}+1$ and $2^n$. Hence the number of steps is between $\log_2 n$ and $1+\log_2 n$. But again notice that $$ \frac{1+\log_2 n}{\log_2 n} \to 1 \qquad \text{ as $n\to \infty$} $$ hence $1+\log_2 n = O(\log_2 n)$.

share|improve this answer

Probably $\log_2 n$. Take $\log_2$ of the # of names and plot that against the # of times. You should get a straight line. In that case, we may say that the algorithm takes $O(\log_2 n)$ comparison.

But wait! $\log_2 n = \log{n}/\log{2}$, i.e. a constant times $\log{n}$. So the algorithm is indeed $O(\log{n})$.

share|improve this answer

There are some "secret" assumptions involved in these kinds of problems, e.g. peoples' names have finite length, say at most $K$ characters, and do not grow with your $n$. Then, I guess you know the drill. You list the names of people (with their associated phone numbers) alphabetically, say as,

Aaron, (314) 159 2654

Anderson, (217) 828 1828

Artichoke, (999) 999 1999

Artin, (123) 456 7890

...

Now, if you want to look for the phone number for Jack, you start from the middle of the list and compare your Jack with the name you see over there (which requires roughly $K$ comparisons by our assumption above). There are three possibilities: If that name matches "Jack," then you are done. If that name comes after Jack alphabetically (such as in the case of "Joe"), then you throw all the names after (and including) that name. Otherwise, you throw all the names before (and including) that name. Now, you have a smaller list (of size $\frac{n}{2}$ or $\frac{n+1}{2}$) and you continue in the same manner with this smaller list you have. Eventually, you will have done (roughly) $K\log_2 n$ comparisons. Since $K$ is independent of $n$, this is $O(\log n)$.

share|improve this answer

The algorithm executes to split the list into parts at each iteration. So, its time complexity depends on the number of times the list is split-- not on how big the split-parts are or into how many splits or anything else. And the algorithm is doing $O(log $ n$)$ splits throughout its execution. "Which logarithm" is "into how many parts" and is irrelevant.

share|improve this answer

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.