how to calculate binary search complexity

Question

Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones:

The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2^x

multiply by 2^x:

2^x = N

now do the log₂:

log₂(2^x)    = log₂ N
x * log₂(2) = log₂ N
x * 1         = log₂ N

this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.

For Binary Search, T(N) = T(N/2) + O(1) // the recurrence relation

Apply Masters Theorem for computing Run time complexity of recurrence relations : T(N) = aT(N/b) + f(N)

Here, a = 1, b = 2 => log (a base b) = 1

also, here f(N) = n^c log^k(n) //k = 0 & c = log (a base b)

So, T(N) = O(N^c log^(k+1)N) = O(log(N))

Source : http://en.wikipedia.org/wiki/Master_theorem

T(n)=T(n/2)+1

T(n/2)= T(n/4)+1+1

Put the value of The(n/2) in above so T(n)=T(n/4)+1+1 . . . . T(n/2^k)+1+1+1.....+1

=T(2^k/2^k)+1+1....+1 up to k

=T(1)+k

As we taken 2^k=n

K = log n

So Time complexity is O(log n)

It doesn't half search time, that wouldn't make it log(n). It decreases it logarithmicly. Think about this for a moment. If you had 128 entries in a table and had to search linearly for your value, it would probably take around 64 entries on average to find your value. That's n/2 or linear time. With a binary search, you eliminate 1/2 the possible entries each iteration, such that at most it would only take 7 compares to find your value (log base 2 of 128 is 7 or 2 to the 7 power is 128.) This is the power of binary search.

The time complexity of the binary search algorithm belongs to the O(log n) class. This is called big O notation. The way you should interpret this is that the asymptotic growth of the time the function takes to execute given an input set of size n will not exceed log n.

This is just formal mathematical lingo in order to be able to prove statements, etc. It has a very straightforward explanation. When n grows very large, the log n function will out-grow the time it takes to execute the function. The size of the "input set", n, is just the length of the list.

Simply put, the reason binary search is in O(log n) is that it halves the input set in each iteration. It's easier to think about it in the reverse situation. On x iterations, how long list can the binary search algorithm at max examine? The answer is 2^x. From this we can see that the reverse is that on average the binary search algorithm needs log2 n iterations for a list of length n.

If why it is O(log n) and not O(log2 n), it's because simply put again - Using the big O notation constants don't count.

Here is wikipedia entry

If you look at the simple iterative approach. You are just eliminating half of the elements to be searched for until you find the element you need.

Here is the explanation of how we come up with the formula.

Say initially you have N number of elements and then what you do is ⌊N/2⌋ as a first attempt. Where N is sum of lower bound and upper bound. The first time value of N would be equal to (L + H), where L is the first index (0) and H is the last index of the list you are searching for. If you are lucky, the element you try to find will be in the middle [eg. You are searching for 18 in the list {16, 17, 18, 19, 20} then you calculate ⌊(0+4)/2⌋ = 2 where 0 is lower bound (L - index of the first element of the array) and 4 is the higher bound (H - index of the last element of the array). In the above case L = 0 and H = 4. Now 2 is the index of the element 18 that you are searching found. Bingo! You found it.

If the case was a different array{15,16,17,18,19} but you were still searching for 18 then you would not be lucky and you would be doing first N/2 (which is ⌊(0+4)/2⌋ = 2 and then realize element 17 at the index 2 is not the number you are looking for. Now you know that you don’t have to look for at least half of the array in your next attempt to search iterative manner. Your effort of searching is halved. So basically, you do not search half the list of elements that you searched previously, every time you try to find the element that you were not able to find in your previous attempt.

So the worst case would be

[N]/2 + [(N/2)]/2 + [((N/2)/2)]/2.....
i.e:
N/2¹ + N/2² + N/2³ +..... + N/2^x …..

until …you have finished searching, where in the element you are trying to find is at the ends of the list.

That shows the worst case is when you reach N/2^x where x is such that 2^x = N

In other cases N/2^x where x is such that 2^x < N Minimum value of x can be 1, which is the best case.

Now since mathematically worst case is when the value of
2^x = N
=> log₂(2^x) = log₂(N)
=> x * log₂(2) = log₂(N)
=> x * 1 = log₂(N)
=> More formally ⌊log₂(N)+1⌋