Skip to main content
added 92 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

The value that you've got is the number of searches required in Worstthe worst case by BSbinary search. Each function call is responsible for only 1 search. And your RRrecurrence relation justifies that. So the RRrecurrence relation you wrote is for the number of searches. Indeed we require logn +1$\log n +1$ searches if itsit's a worst case. Take n=7any $n$,8 say $n=7,8$,any and try and see for yourself. :)

The value that you've got is number of searches required in Worst case by BS. Each function call is responsible for only 1 search. And your RR justifies that. So the RR you wrote is for number of searches. Indeed we require logn +1 searches if its a worst case. Take n=7,8,any and try. :)

The value that you've got is the number of searches required in the worst case by binary search. Each function call is responsible for only 1 search. And your recurrence relation justifies that. So the recurrence relation you wrote is for the number of searches. Indeed we require $\log n +1$ searches if it's a worst case. Take any $n$, say $n=7,8$, and try and see for yourself.

Source Link
SpawN
  • 21
  • 4

The value that you've got is number of searches required in Worst case by BS. Each function call is responsible for only 1 search. And your RR justifies that. So the RR you wrote is for number of searches. Indeed we require logn +1 searches if its a worst case. Take n=7,8,any and try. :)