Prove pela indução de que a forma de recorrência do tipo de bolha é $ \ ômega (n ^ 2) $

Question

A forma de recorrência do tipo de bolha é $ t (n)= t (n-1) + n- 1 $

Como posso provar por indução que isso é $ \ ômega (n ^ 2) $ ?

Estou preso com $ t (n + 1) \ GEQ CN ^ 2 + n= n (CN + 1) $

Answer 1

Assumir $ t (1)= 1 $ , você pode mostrar por indução que $ t (n)= \frac {n (n-1)} {2} + 1 $ .

O caso da base é trivial desde $ t (1)= 1=frac {1 \ cdot 0} {2} + 1 $ .

.

Quanto ao passo indutivo, suponha que a reivindicação mantenha até $ t (n) $ . $ \ begin {alinhar *} 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. \ fim {alinhar *} $