Java – trying to prove that the complexity of binary search is O (log (n))
I tried to prove the complexity of binary search Wikipedia says the worst case scenario is log (n) This means:
If I have an array of 16 elements, log (16) is 4 I should have up to four calls to find elements in the array
My @ L_ 419_ 0 @ Code:
class Main{
int search(int[] array,int number,int start,int end) {
System.out.println("Method call");
int half = (end - start) / 2;
if (array[start + half] == number) {
return array[start + half];
}
if (array[start + half] < number) {
return search(array,number,start + half,end);
} else {
return search(array,start,end - half);
}
}
public static void main(String[] args) {
int[] array = new int[] { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
for (int i : array) {
System.out.println(i);
new Main().search(array,i,array.length);
}
}
}
Ideaone Code: http://ideone.com/8Sll9n
The output is:
1 Method call Method call Method call Method call Method call 2 Method call Method call Method call Method call 3 Method call Method call Method call 4 Method call Method call Method call Method call 5 Method call Method call 6 Method call Method call Method call Method call 7 Method call Method call Method call 8 Method call Method call Method call Method call 9 Method call 10 Method call Method call Method call Method call 11 Method call Method call Method call 12 Method call Method call Method call Method call 13 Method call Method call 14 Method call Method call Method call Method call 15 Method call Method call Method call 16 Method call Method call Method call Method call
Everything is fine except search 1 I have five "method calls", which means that 5 is greater than log (16)
My assumption is that I may have miscalculated the phone number Can someone tell me what's wrong?
Solution
The complexity of binary search for input of size n is O (loga n) for a > 0 1. The essence of the algorithm shows that a = 2, because the search space is halved at each iteration
The code you provided also works properly Confusion about algorithm complexity has occurred because you ignored the constants hidden in the complexity of big Oh representation
The statement f (n) = O (g (n)) indicates that f (n) ≤ CG (n) In your case, you forget to admit that this constant C. C can be very large as 10000000000 or as small as 0.000000001 This is a problem related to the big Oh representation For many practical purposes, since very large or small constants are involved, asymptotically more complex algorithms may perform asymptotically simpler algorithms
For example, compared with algorithm H = 0 (N2), algorithm g = 0 (1000000000 n) will give travel performance because n < 1 1 billion Therefore, the conclusion is that due to the participation of hidden constants, you cannot prove the complexity of the algorithm only by calculating the number of instructions executed You need to have strict mathematical methods to get evidence For example, for the input size n = 10, the algorithm f executing 100 instructions can be, O (n) if C is 10, f (n) = O (10, n) O (N2) if C is 1, then f (n) = O (1 N2) O (N3) if C is 0.1, then f (n) = O (0.1n3)