Can you explain the logarithmic complexity and the search in half to me in plain language

Question

there is an explanation here, but I still do not have a full understanding. What is a simple English explanation of the "Big O" notation?

Answer 1

This is not biggy - you have a list of things in order, in the example in the link you gave, these are the names in the phone book - a good way to find the name

go to the middle of the phone book, is the name you are looking in alphabetical order after the name at the bottom of the page? Yes, then you need to look at the pages after these pages, or if earlier, we need to look at the pages before this page (or we found it). Thus, we have reduced the number of pages that we should look at in the next iteration in half (or divided into two parts).

In our next iteration, we look at either the first half of the phone book or the second half of the phone book. So let's say that the name is in the first half, then we go to the middle of this half, and again our test is the name that we are looking for before or after the names on this page.

etc.

What is the maximum number of times we have to do this? n is the number of pages, so in the worst case, the page we are looking for is in the last iteration. In the last iteration, n should be equal to 1 (or 2), so how many times do we have to cut n in half to get 1. This number is log n base 2, or, as cs says, O (log n) - they just leave the main part 2.

Perhaps another way to look at this, you have the name that you want to find in the phone book. Each time you look in the middle of a book and see if the name you are looking for is in the first or last half of the book. The half name you are looking for is that you hold that half and throw the other half away.

You know that half of the book you saved has the name you are looking for. Repeat the test, open the middle of the book that you saved, and see if the name you are looking for is in the last half or in the first half, save half the book that contains the name, and discard The other half. Continue to do this until you find a name. Hth

Answer 2

Each step of dividing in half approximately doubles the search space. So, after k steps, you have reduced the search space by about 2 ^ k. If initially there were n points in the search space, then after steps log2 (n), the remaining search space consists of only one point.

Of course, the halving method depends on the ability to decide what half the goal is, so you need to sort (in a sense) the input.