How do you calculate a large binary search algorithm?

Question

I am looking for mathematical proof, not just an answer.

Answer 1

binary search recurrence relation is (in the worst case)

T(n) = T(n/2) + O(1)

Using the Main Theorem

• n is the size of the problem.
• a is the number of subtasks in recursion.
• n / b is the size of each subtask. (It is assumed here that all subtasks are essentially the same size.)
• f (n) is the cost of the work performed outside of the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions with the subtasks.

Here a = 1, b = 2 and f (n) = O (1) [Constant]

f (n) = O (1) = O (n ^{log _b a})

= > T (n) = O (n ^{log _b a} log ₂ n)) = O (log ₂ n)

Answer 2

: , , . n log ₂ (n) , :

2 · 2 ·... · 2 · 2 = 2 ^x ≤ n ⇒ log ₂ (2 ^x) = x ≤ log < > 2 > ()

x . O (1) O (log n) .