CODEWITHSUNDEEP
algorithmsearchtime-complexitybinary-searchasymptotic-complexity
Joe
Joe

Reputation: 392

Time complexity for modified binary search which calculates the mid as high - 2

I have to find out the time complexity for binary search which calculates the dividing point as mid = high - 2 (instead of mid = (low + high)/2) so as to know how much slower or faster the modified algorithm would be

Upvotes: 1

Views: 159

Answers (2)

Ayoub Falah
Ayoub Falah

Reputation: 484

Hint: You can derive the answer based on the recurrence formula for binary search.

We have T(n) = T(floor(n/2)) + O(1)

Since we divide in two equal halfs, we have floor(n/2). You should rewrite the given formula to describe the modified version. Furthermore, you should use Akra-Bazzi method to solve the recursion formula for the modified version since you are dividing in two unbalanced halfs.

Upvotes: 1

Lajos Arpad
Lajos Arpad

Reputation: 76424

The worst-case scenario is that the searched item is the very first one. In this case, since you always subtract 2 from n, you will have roughly n/2 steps, which is a linear complexity. The best case is that the searched item is exactly at n-2, which will take a constant complexity. The average complexity, assuming that n -> infinity will be linear as well.

Upvotes: 2

Related Questions