4

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

Community
  • 1
  • 1
lovetolearn
  • 93
  • 1
  • 4
  • 11
  • 1
    possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) I don't think answers get any more clear or complete – Nemo Nov 10 '11 at 15:57

2 Answers2

6

It's no biggy - You have a list of things in order, in the example in the link you gave it is names in a phone book - a good way to find the name is

go to the middle of the phone book, is the name you're looking for alphabetically later than the name at the bottom of the page? Yes then you need to look in the pages after these pages, or if it's before then we need to look in the pages before this page (or we've found it). So we've cut the number of pages we have to look at in the next iteration in half (or bisected it).

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

and so on

What's the maximum number of times we have to do this? n is the number of pages, so in the worse case the page we're looking for is in the last iteration, In the last iteration n must equal 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 the cs people say O(log n) - they just leave out the base 2 part.

Perhaps another way to look at it you have a name you want to find in a phone book. Each time you look in the middle of the book and see if the name you're looking for is in the first or last half of the book. Which ever half the name you're looking for is in you keep this half and throw away the other half.

You know then that the half of the book you kept has the name you're looking for in it. You do the test again, open up the middle of the book you have kept and see if the name you're looking for is in the last half or the first half, keep the half of the book that contains the name and throw away the other half. Keep doing this until you've found the name. hth

daven11
  • 2,905
  • 3
  • 26
  • 43
  • I have a question which came about after reading your answer from the paragraph starting with ( Perhaps). Lets say i am looking for a friends name in my phone book, his name is Neil Alsop. My phone book has 1000 names. I open the book in the middle, and see that his name is not in the first half of the book, i throw away the first half of the book. Now i have a 500 name book, i open it again in the centre to see which side his name is on, and throw another half. – lovetolearn Nov 10 '11 at 13:44
  • so every time i am getting closer to finding his name. While without the Logarithmic search, i would have had to go through every name, so 1000 searches. Is this correct? – lovetolearn Nov 10 '11 at 13:44
  • That is exactly correct. (And going through every name is called a linear search and its O(n)) – daven11 Nov 10 '11 at 23:24
1

Each bisection step roughly halves the search space. So after k steps, you have reduced the search space by a factor of about 2^k. If originally there were n points in the search space, after about log2(n) steps, the remaining search space consists only of a single point.

Of course, the bisection method depends on the possibility to decide in which half the target must lie, so you need sorted (in some sense)input.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431