What is the average time complexity of binary search if the numbers are arranged in descending order and the search is unsuccessful? (a) log2 (n+1) (b) log2 (n) (c) log2 (n^2) (d) None of the following
It should be log2(n). Whether the list is ascending/descending doesn't matter. The worst case complexity will remain the same. In the process, we are dividing the list in terms of mid element, and diving the list into halves every time.
1 = N/2^x => 2^x = N => x = log2(N)