Can someone explain me when it comes to binary search we say the running time complexity is O(log n)? I searched it in Google and got the below,
"The number of times that you can halve the search space is the same as log2 n".
I know we do halve until we find the search key in the data structure, but why we have to consider it as log2 n? I understand that ex is exponential growth and so the log2 n is the binary decay. But I am unable to interpret the binary search in terms of my logarithm definition understanding.
Time Complexity of Binary Search Algorithm is O(log2n). Here, n is the number of elements in the sorted linear array. This time complexity of binary search remains unchanged irrespective of the element position even if it is not present in the array.
The definition of the logarithm says that k is about log2(n), so binary search has that complexity. So basically, in this case log2(𝑛) is simplified as log n in the lecture.
The time complexity of the binary search algorithm is O(log n). The best-case time complexity would be O(1) when the central index would directly match the desired value.
O(N log2N) Time Algorithms of this type typically will apply a logarithmic algorithm N times. Basically that's it. An algorithm that will use O(log n) or Logarithmic a certain number of times to accomplish it's task. The better sorting algorithms, such as Quicksort, Heapsort, and Mergesort, have O(N log2N) complexity.
Think of it like this:
If you can afford to half something m times, (i.e., you can afford to spend time proportional to m), then how large array can you afford to search?
Obviously arrays of size 2m, right?
So if you can search an array of size n = 2m, then the time it takes is proportional to m, and solving m for n look like this:
n = 2m
log2(n) = log2(2m)
log2(n) = m
Put another way: Performing a binary search on an array of size n = 2m takes time proportional to m, or equivalently, proportional to log2(n).
Binary search :-
lets take an example to solve the problem .
suppose we are having 'n' apples and every day half of the apples gets rotten . then after how many days the apple count will be '1'.
first day n apples : a a a a .... (total n)
second day : a a a a..a(total n/2)
third day : a a a .. a(total n/(2^2));
so onn..............
lets suppose after k days the apples left will be 1
i.e n/(2^k) should become 1 atlast
n/(2^k)=1; 2^k=n; applying log to base 2 on both sides
k=log n;
in the same manner in binary search
firstly we are left with n elements then n/2 then n/4 then n/8 so on finally we are left with one ele so time complexity is log n
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With