new to programming - understanding big-O for Binary search

Question

In how many steps would the binary search algorithm halt?

If it were to search for the value 17, in the set S={2,3,5,7,11,13,17,19,23}.

My answer was O(n), which was wrong. The correct answer is: O(log (n)), I am not sure why this is. Can someone explain it to me ?

I actually don't know the difference between O(log(n)) and O(n), can you explain it to me ?

O(log n) is not the correct answer to a question asking for the specific amount of steps an algorithm needs to find a specific number in a specific set of numbers (O(log n) is not a number, its a complexity class). So I guess that the question really was about the complexity of the algorithm. — LionC, Aug 14 '14 at 13:53
i actually dont know the difference between O(log(n)) and O(n), can you explain it to me ? — shmed fred, Aug 14 '14 at 13:57
`[0...8]` => halving point `[4]` ~ 11 ==> `[5...8]` ==> halving point `[6]` = 17 so two steps, isn't it? — EpicPandaForce, Aug 14 '14 at 13:58
You might be looking for http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?lq=1 — EpicPandaForce, Aug 14 '14 at 13:58
This is definitely something that you can find very easily with a simple Google search. — ethanfar, Aug 14 '14 at 15:04

score 0 · Answer 1 · answered Aug 14 '14 at 14:06

Big O notation, in your case, tells you the longest time it will take a given algorithm to find a specific entry in your list.

You said you thought it was O(n). You're saying your algorithm takes (at most) as long as numbers as you have. So essentially your algorithm could be written as:

Look at the first number, is that it?
If not, look at the second number.  Is that it?
....

Taking that route, you can plainly see, will take at most as long as your list is (i.e. trying to find number 23). You didn't state it, but it looks like your list is ordered. You can use that knowledge to use a binary search, which can be described as:

Look at the middle number of the list, is that my number?
If not, is my number bigger than that? 
        Yes - Chop off the left
        No - Chop off the right
Repeat on new list

using that route, your max time to find your number is O(log(n)). Obviously, a binary search must be on an ordered list, or it wouldn't work.

AbcAeffchen · Answer 2 · 2015-01-27T14:22:07.813

binary search takes (given a sorted list) the middle element and checks if this what you are looking for is bigger or not and then checking only the right or the left half for the element you are looking for. In a sortet list you know: if an element is to big, everything at the right of this element is also to big.

You can see the log n complexity this way:

Writing down a balanced binary tree starting with the middle element of the list. the two children are the middle values of the right and the left sublists.
Now the number of leafs in your tree doubles every step. your binary search starts at the root and desides every step to go left or right. The worst case is, that the element you are looking for is not in the list, so if you reach a leaf and it has not the right value, the element is not in the list.

But how many steps your search do? just as many as the depth of your tree. Let this number x. It holds

2^x-1 < n ≤ 2^x => x = ceil( log n )

As big O describes an upper bound you can say binary search runs in O(log n). O(log n) means that you can always find a constant number c such that the steps of the algorithm holds steps < c ⋅ log n.

Side note: if steps < c ⋅ log n holds, then also steps < c ⋅ n so binary search is also in O(n), but O(n) is not close. Instead of O(log n) you can say Θ(log n), which means it taks log n steps, not more not less (except for a constant factor)

new to programming - understanding big-O for Binary search

2 Answers2