What Is the Correct Derivation of Binary Search Complexity?

[apiwowar]

i found the recursive relation which is T(n) = 1 + t(n/2)

after a couple of substitutions i found the pattern which is T(n) = 2^i-1 + T(n/ 2ⁱ)

i chose i = log2 n and then when i plugged it in i got

T(n) - 2^{log2(n -1)} + T(1)

but doesn't the first part simplify to n-1?

the complexity of binary search is O(logn)

where did i mess up?

 

[Mark44]

i found the recursive relation which is T(n) = 1 + t(n/2)

Should be T(n) = 1 + T(n/2), right? Also, in a recursive relationship, there has to be some number at which recursion stops. In that case, it would be T(1), I think, because at some point n/2 will be less than 1.

after a couple of substitutions i found the pattern which is T(n) = 2^i-1 + T(n/ 2ⁱ)

Where did this come from? Just above, you have T(n) = 1 + T(n/2).

i chose i = log2 n and then when i plugged it in i got

T(n) - 2^{log2(n -1)} + T(1)

How did you get this?

but doesn't the first part simplify to n-1?

the complexity of binary search is O(logn)

That's right, assuming the list is in order. Think about a list of 32 numbers. By dividing the list in two, you have two sublists of 16 numbers each. It's pretty easy to tell whether the number you're looking for is in the first list or the second, so you can narrow the search down to on of the 16-element lists.

Now, divide that list into two 8-element lists. Determine which of these lists the number needs to be in.

Divide one of the 8-element lists into two 4-element lists, and determine which half the number needs to be in.

Divide one of the 4-element lists into two 2-element lists, and determine which half the number needs to be in.

Finally, divide one of the 2-element lists into two single-element list. If the number is present in the first place, it will be in one or the other 1-element list.

We divided the 32-element list 5 times to get down to a single number. 32 = 2⁵, and log₂ 32 = 5. The same reasoning can be generalized to lists with n elements.