Best case occurs if x = R[mid] is true the very first time.
Thus,
B(n) = 1
Worst case occurs if x = R[mid] is always false.
Now,
W(0) = 0
W(2k – 1) = 
Solving the recurrence equation to get the closed form using repeated substitution,
W(2k – 1) =
= 1 + [ ]
= 1 + [1 + [ ]]
Repeating ‘i’ times,
W(2k – 1) = 
if ‘i = k’,
W(2k – 1) = k + 0 = k
We want W(n), so
2k – 1 = n
or, lg 2k = lg (n + 1)
or, k = lg (n + 1) {k in terms of n}
Thus,
W(n) = lg (n + 1)
Share with your friends: |
