[Algoritmi] Dimostrazione del tempo di esecuzione di Quicksort nel worst-case

[CosenTheta]

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?

[apatriarca]

Qual'è il significato di \(\Theta(n)\)? Nota che possiamo scegliere il valore di \(c\) a piacere in quanto le relazioni rimangono certamente valide prendendo un \(c\) più grande. Hai che \(\Theta(n)\) è più piccolo di un qualche \(dn\) e quindi sceglierai \(c\) in modo che \(d - 2c\) è negativo e consideri un \(n\) abbastanza grande per cui \((2c - d)n > c\).

[CosenTheta]

Dunque, se ho ben capito, tu hai scelto una delle possibili funzioni lineari dall'insieme $\Theta(n)$, ponendo dunque $\Theta(n) = dn, d > 0$. Quindi la relazione finale diventa

$ cn^2 - 2cn + c + dn \leq cn^2 $
$ -2cn + c + dn \leq 0 $
$ (2c - d)n \geq c $

Qui bisogna necessariamente imporre che la quantità $(2c - d)$ sia positiva.

Volendo invece dimostrare anche che $T(n) = \Omega(n^2)$, usando la definizione ottengo che

$ T(n) \geq c(n - 1)^2 + \Theta(n) = cn^2 - 2cn + c + dn$

Dunque, seguendo lo stesso procedimento di prima, impongo che

$cn^2 - 2cn + c + dn \geq cn^2$
$-2cn + c + dn \geq 0$
$ (2c - d)n \leq c $

Ora, a primo membro ho la quantità $(2c - d)$ che può essere di qualunque segno, mentre $n$ è positivo; quindi il segno a primo membro è quello di $(2c - d)$; a secondo membro ho $c$ che è positiva e il segno di disuguaglianza è $\leq$. Dunque, a primo membro posso avere sia un numero negativo (che è certamente minore di una quantità positiva) che un numero positivo (purchè sia $\leq c$), quindi posso sia imporre che $(2c - d) < 0$ che $(2c - d) > 0$?

[apatriarca]

Devi utilizzare dei \(c\) e \(d\) diversi nelle due dimostrazioni.

[CosenTheta]

Grazie.