2008-8 第1問 (1)

(a)
v = k_j のとき比較回数は j回
探索失敗の場合、比較回数は n回

よって、
C = Σ_j∈[1,n] ( j / 2n ) + n / 2 = (3n + 1) / 4
C_max = n

(b)
C = Σ_j∈[1,n] ( j / 2^j ) + n / 2ⁿ

まず、C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ) を示す。

n = 1のとき、C = 1

Σ_j∈[1,k] ( j / 2^j ) + k / 2^k = 1 + Σ_j∈[1,k-1] (1 / 2^k) とすると、
Σ_j∈[1,k+1] ( j / 2^j ) + (k + 1) / 2^k+1
= Σ_j∈[1,k] ( j / 2^j ) + (k + 1) / 2^k
= 1 + Σ_j∈[1,k-1] (1 / 2^k) + 1 / 2^k
= 1 + Σ_j∈[1,k] (1 / 2^k)

よって、数学的帰納法より、
C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ)

Σ_j∈[1,n-1] (1 / 2ⁿ) < 1 なので、C < 2