Dimostra per induzione che la forma di ricorrenza di bolle ordinaria è $ \ omega (n ^ 2) $

Question

La forma di ricorrenza di bolle ordinamento è $ t (n)= t (n-1) + n- 1 $

Come posso dimostrare di induzione che questa è $ \ omega (n ^ 2) $ ?

Sono bloccato con $ t (n + 1) \ geq cn ^ 2 + n= n (cn + 1) $

Answer 1

Assumendo $ t (1)= 1 $ , puoi mostrare per induzione che $ t (n)= \frac {n (n-1)} {2} + 1 $ .

Il caso base è banale poiché $ t (1)= 1=frac {1 \ clot 0} {2} + 1 $ .

Per quanto riguarda il gradino induttivo, supponiamo che il reclamo detenga fino a $ t (n) $ . $ \ Begin {allinea *} 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 {allinea *} $