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

Question

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 2^x = 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?

Answer 1

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$.