# How is the running-time value (shown in a graph) of log n found in the following problem?

Disclaimer: I could not recall at all the concept of Logarithms, so I watched this first video titled "Logarithms". So now all I really understand is $\log_2 26 = x$ is just the same as 2x = 16. ... That is to say that please keep your jargon extremely simple while answering.

A given problem is that there is a phone directory 1000 pages long, and we are looking for a name "Zurich Smith". The algorithm (i.e. the steps carried out to solve a problem) is:

1. Split the phone directory into half. If the name is in the first half, get rid of the second half; and if the name is in the second half, get rid of the first half. Now we are left with 500 pages.

2. Repeat the above step another time, and we are left with 250 pages.

3. Repeat the above step another time, and we are left with 125 pages.

4. Repeat the above step another time, and we are left with, so to speak, 62.5 pages.

5. Repeat the above step another time, and we are left with, so to speak, 31.25 pages.

6. Repeat the above step another time, and we are left with, so to speak, 15.625 pages.

7. Repeat the above step another time, and we are left with, so to speak, 7.81725 pages.

8. Repeat the above step another time, and we are left with, so to speak, 3.908625 pages.

9. Repeat the above step another time, and we are left with, so to speak, 1.9543125 pages.

10. Repeat the above step another time, and we are left with, so to speak, 0.97715625 pages.

Which is almost 10 steps to solve the problem. But in this lecture that I was watching (watch at 24:30 minutes), they have shown the green line in the following graph to represent this algorithm, and it is labelled log n where n=size of the book.

The question is how did they find out this value?

Like, for an algorithm in which we start at the first page, and turn each page while looking for the name, takes n steps (1000 which is the number of pages) in the worst case (i.e. the case in which the name is on the last page). It is understood.

Likewise, if we turn two pages at a time, it is understood that it will take n/2 steps.

But how log n for the mentioned algorithm?

• You need $10$ steps, because $10$ is the smallest integer greater than or equal to $\log_2 1000$, i.e., $2^9 = 512 < 1000 \leq 1024 = 2^{10}$. Commented Sep 18, 2015 at 13:09

You know that the statement $2^a=16$ is equivalent to the statement $\log_2 16=a$.

Excellent! we'll be using that in a minute.

Let's look at your page turning problem the other way around:

If you have 1 page to look through, the algorithm takes no time at all - it has the correct page selected already! So for $n=1$, $t=0$.

If you have 2 pages, the algorith requires 1 halving, then finds the right page. So for $n=2$, $t=1$.

If you have 4 pages, the algorith requires 2 halvings, then finds the right page. So for $n=4$, $t=2$.

If you have 8 pages, the algorith requires 3 halvings, then finds the right page. So for $n=8$, $t=3$.

It should be pretty clear that $n=2^t$ or $2^t=n$.

Now let's use the equivalence we had earlier...

Therefore $\log_2 n=t$ or $t=\log_2 n$.

• Thank you for your answer, it makes perfect sense, but the problem is that the illustration given (which I cropped from a screenshot of while the video was playing) says $\log n=t$, and not $\log_2 n=t$. :-s Commented Sep 17, 2015 at 22:39
• It just means that it is proportional to $\log n$, which is the same as being proportional to $\log_2 n$.
– tomi
Commented Sep 17, 2015 at 22:41
• @Solace That's one of the interesting things about the logarithm function. No matter what the base of the logarithm is, they are all equal up to a constant. $\log_2(a) = \frac{\log(a)}{\log 2}$.
– 5xum
Commented Sep 17, 2015 at 22:52