Sia $n$ la dimensione della struttura dati in ingresso all'algoritmo Quicksort. Il caso peggiore (che capita quando il partizionamento produce due sottostrutture completamente sbilanciate, ossia una con nessun elemento e un'altra con $n-1$ elementi) si può descrivere con la ricorrenza
$T(n) = T(0) + T(n-1) + \Theta(n) = T(n-1) + \Theta(n)$.
Si vuole dimostrare che $T(n) = \Theta(n^2)$ utilizzando il metodo di sostituzione.
Per fare questo, è necessario dimostrare (sempre tramite tale metodo) che $T(n) = O(n^2)$ e $T(n) = \Omega(n^2)$.
La dimostrazione per il primo caso, con l'utilizzo della definizione di O-grande, è riportata come segue
$T(n) \leq c(n - 1)^2 + \Theta(n) = cn^2 - 2cn + c + \Theta(n) \leq cn^2$.
L'ultima maggiorazione è giustificata dicendo che "si sceglie un $c$ sufficientemente grande per cui il termine $-2cn + c$ supera $\Theta(n)$". Come dimostro matematicamente che effettivamente esiste un tale $c_0$ sufficientemente grande per cui si verifica quanto detto?