情報科学に関連した問題に関するチートシートです(自分用なため、内容が偏っている可能性が大きいです)。
漸化式から最悪計算時間の一般項を算出
$\alpha,\beta$を定数とする。
このとき、自然数$n(\ge1)$の大きさの入力データを処理するアルゴリズムの最悪計算時間$T(n)$の漸化式が次のように与えられたとする。
T(n)=\alpha T\left(\left\lfloor \frac{n}{\beta} \right\rfloor\right)+f(n)
(n)がn次式のとき
T(n) = \sum_{i=0}^{\log_\beta n} \alpha^i f\left(\frac{n}{\beta^i}\right)
f(n)が定数のとき
\begin{align}
T(n) &= \sum_{i=0}^{\log_\beta n} \alpha^i f(n) \\
&= \frac{\alpha^{\log_\beta n+1}-1}{\alpha-1} f(n)
\end{align}