How to understand that sequence is logarithmic?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.