Prouver par induction que la forme de récurrence de tri de bulles est $ \ oméga (n ^ 2) $

Question

La forme de récurrence de tri de bulles est $ t (n)= t (n-1) + n- 1 $

Comment puis-je prouver par induction que c'est $ \ omega (n ^ 2) $ ?

Je suis coincé avec $ t (n + 1) \ geq cn ^ 2 + n= n (cn + 1) $

Answer 1

supposer $ t (1)= 1 $ , vous pouvez montrer par induction que $ t (n)= \frac {n (n-1)} {2} + 1 $ .

Le boîtier de base est trivial depuis $ t (1)= 1=frac {1 \ CDOT 0} {2} + 1 $ .

.

Quant à l'étape inductive, supposons que la réclamation conserve jusqu'à $ T (n) $ . $ \ commencez {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. \ fin {align *} $