Week 2: Analysis of Algorithms, Dynamic Data Structures (43)

43

Example: Binary Search (cont)

Cost analysis:

C_i = #calls to search() for array of length i
for best case, C_n = 1
for a[i..j], j<i (length=0)
- C₀ = 0
for a[i..j], i≤j (length=n)
- C_n = 1 + C_n/2 ⇒ C_n = log₂ n

Thus, binary search is O(log₂ n) or simply O(log n) (why?)