分類された配列からのバランスの取れたBSTを構築することを証明することは$ \ theta（n）$です

Question

【課題】【SPAN CLASS="Math-Container"> $¥theta（n）$

です。

次の式を手に入れました。 $$ t（n）= 2t（\ frac {n} {2}）+ \ theta（1）$$

私は誘導によってそれを証明しようとしましたが、 $ n $ が奇数です。

それを証明するためのより良い方法はありますか？置換は有効な証明と見なされない（私はコースの置換を使用して閉学式に達しました）。

Answer 1

Master Theorem 次に、すぐに締めくくることができます。その $ t（n）=theta（n）$ （ $ n ^ {\ log_2 2}= n=OMEGA（1）$ ）

マスター定理を使用することができない場合は、代わりにこの再発を書くことができます。 $$ T（N）\ LE 2T（\ LFLOOR N / 2 \ RFLOOR）+ C、 $$ $ c> 0 $ は絶対定数と $ t（1）\ le c $ です。< / P>

その後、 $ t（n）\ le 2cn - c $ という誘導によって証明することができます。 基本ケースは $ n= 1 $ です。 $ t（1）\ le c= 2cn - c $ 。 $ n> 1 $ を考慮し、請求が $ n-1 $ まで成り立つとします。 $ n $ を保持することを証明します。 $$ T（n）= 2T（\ LFLOOR N / 2 \ RFLOOR）+ C \ LE 2（2C \ LFLOOR N / 2 \ RFLOOR-C）+ C \ LE 2cn - 2c + C= 2cn - c。 $$