繰り返しを解決しているときに、床と天井が無視されている場所に出くわしました。
床が無視されているCLRS （第4章、pg.83）の例：
ここ( pg.2、演習 4.1–1 ) は、上限が無視される例です: (編集: これはやや怪しいという世論から収集します。)
実際、CLRS（pg.88）では、次のように述べられています。
「再発を解決するとき、床と天井は通常重要ではありません」
私の質問:
注: これは宿題の問題ではありません。DS とアルゴリズムの概念を再確認しているときに考えました。
床関数と天井関数は、すべてのx に対して次の不等式を満たします。
x −1 < ⌊ x ⌋ ≤ x
x ≤ ⌈ x ⌉ < x +1
したがって、最初の例では、⌊ n / 2⌋ ≤ n / 2 となります。また、対数は単調増加関数であるため、lg ⌊ n / 2⌋ ≤ lg( n / 2) であることがわかります。これらをまとめると、最初の不等式 2( c ⌊ n / 2⌋ lg ⌊ n / 2⌋) + n ≤ cn lg( n / 2) + nが得られます。
2 番目の例には、実際にはエラーが含まれています。c lg ⌈ n / 2⌉ + 1 は、 c lg( n / 2) + 1より小さいことはありませんが、等しくなる可能性があります。ただし、 c lg ⌈ n / 2⌉ + 1 ≤ c lg( n / 2 + 1) + 1 であり、これを上から、たとえばc lg( n / 2) + 2 ( n ≥ 2 と仮定)によってバインドし、 T ( n ) ∈ O (lg n ) です。
実際、2 番目の例には他のエラーも含まれています。次の段落 (引用していません) に記載されている仮定を使用しても、最後の = 記号は ≤ である必要があります。
(Ps. ふー、これは LaTeX なしで入力するのは本当に苦痛でした。それが、他に何もないとしても、これらのような質問はmath.SEで尋ねたほうがよい理由です。)
どちらの例も、マスター定理による分析に適しています。Akra–Bazziの定理は、マスター定理を一般化し、小さな摂動を無視できる場合の十分な条件を提供します（摂動h（x）はO（x / log 2 x）です）。Akra–Bazziによって分析可能な整数インデックスの漸化式の場合、摂動は最大で1であるため、床と天井は常に無視できます。
Akra–Bazziでカバーされていないすべての再発は、アルゴリズムとデータ構造のコンテキストでは非常にエキゾチックです。