通过诱导证明泡沫排序的复发形式是$ \ω（n ^ 2）$

Question

泡沫排序的复发形式是 $ t（n）= t（n-1）+ n-1 $

如何通过诱导来证明这是 $ \ omega（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。 \结束{align *} $