帰還形のバブルソートが$ \ omega（n ^ 2）$の誘導によって証明する

Question

バブルソートの再発形式は $ t（n）= t（n-1）+ n- 1 $

です。

これが $ \ omomega（n ^ 2）$ ？

の誘導で証明する方法

$ t（n + 1）\ geq cn ^ 2 + n= n（cn + 1）$

Answer 1

$ t（1）= 1 $ を仮定すると、 $ t（n）= \という誘導によって表示できます。FRAC {N（N-1）} {2} + 1 $ 。

$ t（1）= 1=frac {1 \ cdot 0} {2} + 1 $

ですので、ベースケースは簡単です。

誘導ステップは、請求が $ t（n）$ まで成り立つとします。 $ \ begin {align *} t（n + 1）＆= t（n）+（n + 1） - 1=frac {n（n-1）} {2} + 1 + n \\ ＆=frac {n ^ 2 -n + 2n} {2} + 1=frac {n ^ 2 + n} {2} + 1=frac {n（n + 1）} {2} + 1 \\ ＆=frac {（n + 1）（（n + 1） - 1）} {2} + 1。 \ end {align *} $