二分探索の時間計算量解析

以下の二分探索アルゴリズムについて、時間計算量を一般化してみます。

def binarySearch(A:list[int],t:int,low:int,high:int) -> int:
    if high < low:
        return -1
    mid: int = (low+high)//2
    tmp: int = A[mid]
    if t == tmp:
        return mid
    elif t<tmp:
        return binarySearch(A,t,low,mid-1)
    elif t>tmp:
        return binarySearch(A,t,mid+1,high)

時間計算量の一般化

$T(n) \left\{ \begin{align} \Theta(1)　\qquad if\quad n = 0 \\T(\frac{n}{2}) + \Theta(1)\qquad if\quad n> 0\end{align} \right.$

よって、

$T(n) = T(\frac{n}{2}) + \Theta(1) $

$n=2^k$とすると、

$T(2^k) = T(2^{k-1}) + \Theta(1) $

$S(k) = S(k-1) + \Theta (1) \qquad where \:\: S(k) = T(2^k)$

この時、

$\Delta = S(k)-S(k-1) = \Theta(1)$より、

$$S(n)-S(1) = \sum_{k=2}^n S(k)-S(k-1)=\sum_{k=2}^n \Theta(1) = \Theta(n)$$

$S(n) = \Theta(n)+S(1)=\Theta(n)$

$n=2^k$より、

$T(n) = T(2^k)=S(k)=\Theta(k)=\Theta(\log n)$

よって、

$T(n)= \Theta(\log n)$