どのように再帰バイナリ検索の実行時間を見つけるには？ - アルゴリズム、ランタイム、ビッグオー、プロシージャ

以下の各手順で、T（n）を実行時間とします。 T（n）の次数を見つけます（つまり、T（n）∈（f（n））となるf（n）を見つけます。

Procedure BinarySearch(table T [a . . . b], int k):
if a > b then
return -1
end if
middle ← ⌊(a + b)/2⌋
if T [middle] = k then
return middle
end if
if k < T [middle] then
return BinarySearch(T [a . . .middle], k)
else
return BinarySearch(T [middle . . . b], k)
end if

単純な関数の実行時間を見つける方法は知っていますが、これには再帰呼び出しが含まれているため、問題が発生しています。

回答：

このリンク （ページの下部）は、バイナリ検索アルゴリズムの再帰関係を解決する非常に明確な方法を示しています。