[algorithm] how to calculate binary search complexity

I heard somebody say that since binary search halves the input required to search hence it is log(n) algorithm. Since I am not from a mathematics background I am not able to relate to it. Can somebody explain it in a little more detail? Does it have to do something with the logarithmic series?

A binary search works by dividing the problem in half repeatedly, something like this (details omitted):

Example looking for 3 in [4,1,3,8,5]

1. Order your list of items [1,3,4,5,8]
2. Look at the middle item (4),
   • If it is what you are looking for, stop
   • If it is greater, look at the first half
   • If it is less, look at the second half
3. Repeat step 2 with the new list [1, 3], find 3 and stop

It is a bi-nary search when you divide the problem in 2.

The search only requires log2(n) steps to find the correct value.

I would recommend Introduction to Algorithms if you want to learn about algorithmic complexity.

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?

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.

Let me make it easy for all of you with an example.

For simplicity purpose, let's assume there are 32 elements in an array in the sorted order out of which we are searching for an element using binary search.

1 2 3 4 5 6 ... 32

Assume we are searching for 32. after the first iteration, we will be left with

17 18 19 20 .... 32

after the second iteration, we will be left with

25 26 27 28 .... 32

after the third iteration, we will be left with

29 30 31 32

after the fourth iteration, we will be left with

31 32

In the fifth iteration, we will find the value 32.

So, If we convert this into a mathematical equation, we will get

(32 X (1/2⁵)) = 1

=> n X (2^-k) = 1

=> (2^k) = n

=> k log₂2 = log₂n

=> k = log₂n

Hence the proof.

Let's say the iteration in Binary Search terminates after k iterations. At each iteration, the array is divided by half. So let’s say the length of the array at any iteration is n At Iteration 1,

Length of array = n

At Iteration 2,

Length of array = n/2

At Iteration 3,

Length of array = (n/2)/2 = n/22

Therefore, after Iteration k,

Length of array = n/2k

Also, we know that after After k divisions, the length of the array becomes 1 Therefore

Length of array = n/2k = 1
=> n = 2k

Applying log function on both sides:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Therefore,

As (loga (a) = 1)
k = log2 (n)

Hence the time complexity of Binary Search is

log2 (n)

Here is the solution using the master theorem, with readable LaTeX.

For each recurrence in the recurrence relation for binary search, we convert the problem into one subproblem, with runtime T(N/2). Therefore:

Substituting into the master theorem, we get:

Now, because is 0 and f(n) is 1, we can use the second case of the master theorem because:

This means that:

Since we cut down a list in to half every time therefore we just need to know in how many steps we get 1 as we go on dividing a list by two. In the under given calculation x denotes the numbers of time we divide a list until we get one element(In Worst Case).

1 = N/2x

2x = N

Taking log2

log2(2x) = log2(N)

x*log2(2) = log2(N)

x = log2(N)

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

ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2

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

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

...

T(N) = T(N/N) + (1 + 1 + 1 +... + 1) = 1 + logN (base 2 log) = 1 + logN

So the time complexity of binary search is O(logN)

Log2(n) is the maximum number of searches that are required to find something in a binary search. The average case involves log2(n)-1 searches. Here's more info:

http://en.wikipedia.org/wiki/Binary_search#Performance

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.