Algoritmi e Strutture Dati Notes

Algoritmi, Efficienza e RAM

Algoritmi e Strutture Dati

• L'informatica è definita come la scienza degli algoritmi che descrivono e trasformano l'informazione.

• Un algoritmo è una sequenza di comandi elementari e univoci che terminano in un tempo finito e operano su strutture dati.

• I comandi elementari non possono essere ulteriormente scomposti e sono univoci.

• Un algoritmo ben specificato non richiede che l'esecutore pensi, ma solo che esegua i passi precisamente.

• Se un calcolatore produce un output errato, è colpa del progettista dell'algoritmo, non del calcolatore.

• Le strutture dati sono necessarie per gestire i dati utilizzati dall'algoritmo, organizzandoli e memorizzandoli per semplificare l'accesso e la modifica.

Efficienza di un algoritmo

• Non esiste una struttura dati adatta a ogni problema; è necessario conoscere i vantaggi e gli svantaggi delle principali strutture dati.

• La scelta della struttura dati è fondamentale quanto la progettazione dell'algoritmo.

• L'efficienza di un algoritmo si misura in termini di tempo di esecuzione e quantità di memoria richiesta.

• I calcolatori sono veloci ma non infinitamente.

• La memoria è economica ma non gratuita né illimitata.

• Il costo computazionale degli algoritmi è valutato in termini di numero di operazioni elementari e quantità di memoria necessaria in funzione della dimensione dell'input.

• Esempio: Ordinamento di $n = 10^6$ numeri interi.

  • Calcolatore V: $10^9$ operazioni/sec

  • Calcolatore L: $10^7$ operazioni/sec

  • Algoritmo Insertion Sort (IS): $2n^2$ operazioni

  • Algoritmo Merge Sort (MS): $50n \cdot log_2(n)$ operazioni

  • Costo temporale:

    • $V(IS) = (2 \cdot (10^6)^2) / (10^9) = 2000 \text{ sec} \approx 33 \text{ min}$

    • $L(MS) = (50 \cdot 10^6 \cdot log_2(10^6)) / (10^7) \approx 100 \text{ sec} \approx 1.5 \text{ min}$

• Aumentando l'input a $n = 10^7$:

  • $V(IS) \approx 55.5$ ore $\approx 2.3$ giorni

  • $L(MS) \approx 19.5$ min

Random Access Machine (RAM)

• Per valutare l'efficienza di un algoritmo, è necessario quantificare le risorse richieste senza essere influenzati dalla tecnologia specifica.

• La Random Access Machine (RAM) è una macchina astratta con le seguenti caratteristiche:

  • Singolo processore che esegue le operazioni sequenzialmente.

  • Operazioni elementari con tempo di esecuzione costante.

  • Limite alla dimensione di ogni valore memorizzato.

Misura di Costo Uniforme

• Sia $d$ la dimensione di bit di ogni parola in memoria.

• Se ogni dato in input è minore di $2^d$, ogni operazione elementare sui dati viene eseguita in tempo costante (misura di costo uniforme).

• Se un dato non rispetta tale ipotesi, sono necessarie più parole di memoria, e le operazioni richiedono un tempo non costante.

• In ambito scientifico si utilizza la misura di costo logaritmica, ma in questo corso non verrà analizzata.

• Esempio:

  • Codice:
    def PotenzaDi2(n): x = 1 for i in range(n): x = x*2 return x

  • Il tempo di esecuzione è proporzionale a $n$, poiché il ciclo viene eseguito $n$ volte, con tre operazioni di costo unitario ad ogni iterazione.

Notazione Asintotica

Notazione O grande, Omega e Teta

• La notazione asintotica permette di valutare l'efficienza di un algoritmo confrontandone il costo computazionale con altri algoritmi.

• Ci si limita a valutare il tasso di crescita, cioè la velocità con cui il tempo di esecuzione cresce all'aumentare della dimensione dell'input.

• La valutazione è efficace quando la dimensione dell'input è sufficientemente grande.

• La notazione asintotica confronta il tasso di crescita di una funzione rispetto a un'altra.

• Esistono tre tipologie principali di notazione asintotica:

  • O grande: limite superiore asintotico.

  • $\Omega$ (Omega): limite inferiore asintotico.

  • $\Theta$ (Teta): limite asintotico stretto.

Notazione O grande

• Definizione: Date due funzioni $f(n), g(n) \geq 0$, $f(n)$ è in $O(g(n))$ se esistono due costanti $c$ ed $n<em>0$ tali che $0 \leq f(n) \leq c \cdot g(n)$ per ogni $n \geq n</em>0$.

• $O(g(n))$ contiene tutte le funzioni "dominate" da $g(n)$.

• La notazione O grande definisce il limite superiore asintotico di $f(n)$:

  • Oltre un certo valore $n_0$, $f(n)$ è limitata da $c \cdot g(n)$.

• Esempi:

  • $f(n) = 3n + 3$ è in $O(n^2)$, con $c = 6$ e $n_0 = 1$

  • $f(n) = 3n + 3$ è in $O(n)$, con $c \geq 6$ e $n_0 = 1$

  • $f(n) = n^2 + 4n$ è in $O(n^2)$, con $c \geq 5$ e $n_0 = 1$

• Teorema: Sia $f(n) = \sum<em>{i=0}^{m} a</em>i n^i = a<em>0 + a</em>1 n + a<em>2 n^2 + … + a</em>m n^m$ un polinomio di grado $m$, allora $f(n)$ è in $O(n^m)$. Dimostrazione per induzione:

  • Caso base: $m=0$, per cui $f(n)= a_0 \cdot n^0$, dunque è una funzione costante e di conseguenza è in $O(1)$, che coincide con $O(n^0)$

  • Ipotesi induttiva: --> Affermiamo che $\sum<em>{i=0}^{k} a</em>in^i$ è un $O(n^k)$ per ogni k < m, cioè esiste una costante c' tale che $\sum<em>{i=0}^{k} a</em>in^i \leq c'\cdot n^k$

  • Passo induttivo: --> Dobbiamo dimostrare che $f(n)=\sum<em>{i=0}^{m} a</em>in^i \leq c''\cdot n^m$
    Si osservi che, mettendo in evidenza l'ipotesi induttiva, f(n) può essere riscritto come
    $f(n) = \sum<em>{i=0}^{m} a</em>in^i = a<em>mn^m + \sum</em>{i=0}^{k} a<em>in^i$ per ogni $k{i=0}^{k} ain^i \leq c'\cdot n^k$ dunque possiamo formulare la seguente catena di disuguaglianze $f(n) = amn^m + \sum{i=0}^{k} ain^i \leq amn^m + c'\cdot n^k \leq amn^m + c'\cdot n^m$
    ricrivendo $amn^m + c'\cdot n^m$ come $(am + c')\cdot n^m$e ponendo $c'' = a_m + c'$ otteniamo che $f(n) \leq c''\cdot n^m$
    che per ipotesi sappiamo essere vera, dunque concludiamo che $f(n)$, è in $O(n^m)$

Notazione Omega

• Definizione: Date due funzioni $f(n), g(n) \geq 0$, $f(n)$ è in $\Omega(g(n))$ se esistono due costanti $c$ ed $n0$ tali che $f(n) \geq c \cdot g(n)$ per ogni $n \geq n0$.

• $\Omega(g(n))$ contiene tutte le funzioni che "dominano" la funzione $g(n)$.

• La notazione Omega definisce il limite inferiore asintotico di $f(n)$:

  • Oltre un certo valore $n_0$, $f(n)$ è limitata inferiormente da $c \cdot g(n)$.

• Esempi:

  • $f(n) = 2n^2 + 3$ è in $\Omega(n)$, con $c = 1$

  • $f(n) = 2n^2 + 3$ è in $\Omega(n^2)$, con $c \leq 2$

• Teorema: Sia $f(n) = \sum{i=0}^{m} ai n^i = a0 + a1 n + a2 n^2 + … + am n^m$ un polinomio di grado $m$, allora $f(n)$ è in $\Omega(n^m)$.

• La dimostrazione è analoga alla dimostrazione del teorema per la notazione O grande.

Ordini di grandezza di O grande ed Omega

• $f(n) = log(n)$ è in $O(\sqrt{n})$ e in $\Omega(1)$.

  • $log_a(n) = O(\sqrt[b]{n})$ per ogni $a, b \geq 1$

  • $n^a = \Omega(1)$ per ogni $a$

  • Un poli-logaritmo è dominato da qualunque radice e domina qualunque costante.

• $f(n) = \sqrt[a]{n}$ è in $O(n)$ e in $\Omega(log(n))$.

  • $\sqrt[a]{n} = O(n^b)$ per ogni $a, b \geq 1$

  • $\sqrt[a]{n} = \Omega(log_b(n))$ per ogni $a, b \geq 1$

  • Una radice è dominata da qualunque polinomio e domina qualunque poli-logaritmo.

• $f(n) = n^a$ è in $O(2^n)$ e in $\Omega(\sqrt[b]{n})$.

  • $n^a = O(b^n)$ per ogni $a \geq 1$ ed ogni $b \geq 2$

  • $n^a = \Omega(\sqrt[b]{n})$ per ogni $a, b \geq 1$

  • Un polinomio è dominato da qualunque esponenziale e domina qualunque radice.

• Scala degli ordini di grandezza (per $n \rightarrow +\infty$):
  $1 \prec log_a(n) \prec \sqrt[b]{n} \prec n^c \prec d^n \prec n! \prec n^n$

Notazione Teta

• Definizione: Date due funzioni $f(n), g(n) \geq 0$, $f(n)$ è in $\Theta(g(n))$ se esistono tre costanti $c1, c2$ ed $n0$ tali che $c1 \cdot g(n) \leq f(n) \leq c2 \cdot g(n)$ per ogni $n \geq n0$.

• Se $f(n)$ è sia in $O(g(n))$ sia in $\Omega(g(n))$, allora è anche in $\Theta(g(n))$.

• La notazione Teta rappresenta il limite stretto asintotico della funzione.

Calcolo delle Notazioni Asintotiche con i Limiti

• \lim_{n\to+\infty} \frac{f(n)}{g(n)} = k > 0 \Rightarrow f(n) = \Theta(g(n))

• $\lim_{n\to+\infty} \frac{f(n)}{g(n)} = +\infty \Rightarrow f(n) = \Omega(g(n)) \text{ ma } f(n) \neq \Theta(g(n))$

• $\lim_{n\to+\infty} \frac{f(n)}{g(n)} = 0 \Rightarrow f(n) = O(g(n)) \text{ ma } f(n) \neq \Theta(g(n))$

• Se il limite del rapporto tra $f(n)$ e $g(n)$ non esiste, allora è necessario procedere diversamente.

Algebra della Notazione Asintotica

• Per semplificare il calcolo del costo computazionale tramite limite asintotico degli algoritmi, si possono utilizzare tre regole algebriche:

  • Regola delle costanti moltiplicative.

  • Regola della commutatività con somma.

  • Regola della commutatività con prodotto.

Regola delle Costanti Moltiplicative

• Per ogni k > 0 e per ogni $f(n) \geq 0$, se $f(n)$ è in $O(g(n))$, allora anche $k \cdot f(n)$ è in $O(g(n))$.

• Per ogni k > 0 e per ogni $f(n) \geq 0$, se $f(n)$ è in $\Omega(g(n))$, allora anche $k \cdot f(n)$ è in $\Omega(g(n))$.

• Per ogni k > 0 e per ogni $f(n) \geq 0$, se $f(n)$ è in $\Theta(g(n))$, allora anche $k \cdot f(n)$ è in $\Theta(g(n))$.

• Le costanti moltiplicative possono essere ignorate durante il calcolo di un qualsiasi limite asintotico.

• Attenzione: La costante moltiplicativa non deve essere all'esponente della funzione (es: in $f(n)=2^{k \cdot n}$ non possiamo ignorare la $k$).

Regola della Commutatività con Somma

• Sia $f(n) = p(n) + q(n)$. Per ogni p(n), q(n) > 0, vale che:

  • Se $p(n)$ è in $O(g(n))$ e $q(n)$ è in $O(h(n))$, allora $f(n)$ è in $O(g(n) + h(n)) = O(max(g(n), h(n)))$.

  • Se $p(n)$ è in $\Omega(g(n))$ e $q(n)$ è in $\Omega(h(n))$, allora $f(n)$ è in $\Omega(g(n) + h(n)) = \Omega(max(g(n), h(n)))$.

  • Se $p(n)$ è in $\Theta(g(n))$ e $q(n)$ è in $\Theta(h(n))$, allora $f(n)$ è in $\Theta(g(n) + h(n)) = \Theta(max(g(n), h(n)))$.

• Un qualsiasi limite asintotico di $f(n)$ è uguale al massimo tra il limite asintotico di $p(n)$ e di $q(n)$.

Regola della Commutatività con Prodotto

• Sia $f(n) = p(n) \cdot q(n)$. Per ogni p(n), q(n) > 0, vale che:

  • Se $p(n)$ è in $O(g(n))$ e $q(n)$ è in $O(h(n))$, allora $f(n)$ è in $O(g(n) \cdot h(n))$.

  • Se $p(n)$ è in $\Omega(g(n))$ e $q(n)$ è in $\Omega(h(n))$, allora $f(n)$ è in $\Omega(g(n) \cdot h(n))$.

  • Se $p(n)$ è in $\Theta(g(n))$ e $q(n)$ è in $\Theta(h(n))$, allora $f(n)$ è in $\Theta(g(n) \cdot h(n))$.

• Un qualsiasi limite asintotico di $f(n)$ è uguale al prodotto tra il limite asintotico di $p(n)$ e di $q(n)$.

Esercizi svolti sull’algebra asintotica

1. Trovare il limite asintotico stretto di $f(n) = 3n^2 + 7$:
   $f(n) = 3n^2 + 7 = \Theta(n^2) + \Theta(1) = \Theta(n^2)$

2. Trovare il limite asintotico stretto di $f(n) = 3n2^n + 4n^4$:
   $f(n) = 3n2^n + 4n^4 = \Theta(n2^n) + \Theta(n^4) = \Theta(n2^n)$

3. Trovare il limite asintotico stretto di $f(n) = 2^{2n}$:
   $f(n) = 2^{2n} = 2^n \cdot 2^n = \Theta(2^n) \cdot \Theta(2^n) = \Theta(2^{2n})$

4. Trovare il limite asintotico stretto di $f(n) = logn(n) + 8 \cdot 2^{n\cdot log(n)} + 3$: $f(n) = logn(n) + 8 \cdot 2^{n\cdot log(n)} + 3 = logn(n) + 8 \cdot 2^{log(n^n)} + 3$ $= logn(n) + 8 \cdot n^n + 3 = \Theta(log_n(n)) + \Theta(n^n) + \Theta(1) = \Theta(n^n)$

5. Trovare il limite asintotico stretto di $f(n) = n^2 \cdot log(n)$:
   $f(n) = n^2 \cdot log(n) = \Theta(n^2) \cdot \Theta(log(n)) = \Theta(n^2 \cdot log(n))$

6. Trovare il limite asintotico stretto di $f(n) = 3n \cdot log(n) + 2n^2$:
   $f(n) = 3n\cdot log(n) + 2n^2 = \Theta(n)\cdot\Theta(log(n)) + \Theta(n^2) = \Theta(n\cdot log(n)) + \Theta(n^2) = \Theta(n^2)$

7. Trovare il limite asintotico stretto di $f(n) = 2^{log(n)/2} + 5n$:
   $f(n) = 2^{log(n)/2} + 5n = (2^{log(n)})^{1/2} + 5n = \sqrt{n} + 5n = \Theta(\sqrt{n}) + \Theta(n) = \Theta(n)$

8. Trovare il limite asintotico stretto di $f(n) = 4^{log(n)}$:
   $f(n) = 4^{log(n)} = (2^2)^{log(n)} = (2^{log(n)})^2 = n^2 = \Theta(n^2)$

9. Trovare il limite asintotico stretto di $f(n) = \sqrt{2^{log(n)}}$
   $f(n) = \sqrt{2^{log(n)}} = 2^{(1/2)\cdot log(n)} = \sqrt{2^{log(n)}} = \sqrt{n} = \Theta(\sqrt{n})$

Sommatorie e Tecniche di dimostrazione

• Dimostrare o confutare la seguente proposizione
  $f(n) = 4^n$ è in $O(2^n)$
  Tramite l’algebra asintotica, siamo già in grado di rispondere a tale proposizione::
  $4^n = 2^{2n} = 2^{n} \cdot 2^{n} = O(2^n)\cdot O(2^n) = O(2^{2n})$
  Dunque, la proposizione è falsa.
  Dimostrazione per assurdo:
  supponiamo che $f(n) = O(2^n)$. Allora abbiamo che $\exists c, n0 | f(n) \leq c \cdot 2^{n} , \forall n \geq n0$
  $4^n \leq c \cdot 2^{n}$
  $2^n \cdot 2^{n} \leq c \cdot 2^{n}$
  $2^{n} \leq c$ Falso una volta superato un certo valore $n_0$

• Dimostrare la seguente proposizione $f(n) = (n + 10)^3$ è in $\Theta(n^3)$

  • Per dimostrare che sia $\Theta(n^3)$, dimostriamo che sia in $O(n^3)$ e in $\Omega(n^3)$:

    • Al crescere di n, esisterà un valore $n0 = 10$ tale che $(n + 10)^3 = (n + n0)^3 \leq (n + n)^3 = (2n)^3 = 8n^3 = O(n^3)$

    • Poiché 10 > 0, si vede facilmente che $(n + 10)^3 \geq (n + 0)^3 = n^3 = \Omega(n^3)$
      Poiché $f(n)$ è sia in $O(n^3)$, sia in $\Omega(n^3)$, allora è anche in $\Theta(n^3)$

• Dimostrare la seguente proposizione $Sn = \sum{k=1}^n k$ è in $\Theta(n^2)$

  • Come nell’esempio precedente, per dimostrare che sia $\Theta(n^2)$, dimostriamo che sia in $O(n^2)$ e in $\Omega(n^2)$:

  • Per dimostrare che $Sn$ è in $O(n^2)$, è necessario fare un "salto logico". Partiamo riscrivendo la sommatoria in forma estesa $Sn = 1 + 2 + 3 + … + (n − 1) + n$
    Notiamo come ogni singolo termine della sommatoria sia $\leq n$. Dunque, possiamo scrivere la seguente disequazione:
    $1 + 2 + 3 + … + (n − 1) + n \leq n + n + n + … + n + n$
    Nella parte destra della disequazione, dunque, abbiamo una somma di n volte n, riscrivibile come $n \cdot n$
    $Sn \leq n \cdot n \Rightarrow Sn \leq n^2$
    A questo punto, ci basta notare che $n^2$ è in $O(n^2)$ e quindi che, poiché $Sn \leq n^2$, di conseguenza anche $Sn$ è in $O(n^2)$.
    Dimostriamo ora che $f(n) = \Omega(n^2)$ in modo analogo a quello precedente. Riscriviamo nuovamente la sommatoria in forma estesa
    $Sn = 1 + 2 + 3 + … + (n − 2) + (n − 1) + n$ Questa volta, notiamo che essa può essere divisa a metà, ottenendo due categorie: $1 + 2 + 3 + 4 + 5 + …$ Numeri $\leq \frac{n}{2}$ $… + (n − 2) + (n + 1) + n$ Numeri $\geq \frac{n}{2}$ A questo punto, è necessario effettuare un ulteriore "salto logico": sappiamo che tutti i numeri minori di $\frac{n}{2}$ sono anche maggiori di 0, mentre quelli maggiori di $\frac{n}{2}$ sono ovviamente maggiori di $\frac{n}{2}$. Dunque, possiamo scrivere la seguente disequazione: $1 + 2 + 3 + … + (n − 2) + (n − 1) + n \geq 0 + 0 + 0 + …$ $\frac{n}{2}$ volte $… + \frac{n}{2} + \frac{n}{2} + \frac{n}{2}$ $\frac{n}{2}$ volte $Sn \geq \frac{n}{2} \cdot \frac{n}{2} \Rightarrow Sn \geq \frac{1}{2} n^2$ A questo punto, ci basta notare che $\frac{1}{2}n^2$ è in $\Omega(n^2)$ e quindi che, poiché $Sn \geq \frac{1}{2}n^2$, di conseguenza anche $Sn$ è in $\Omega(n^2)$. Poiché $Sn$ è sia in $O(n^2)$, sia in $\Omega(n^2)$, allora è anche in $\Theta(n^2)$

• Vediamo ora un ulteriore modo per poter dimostrare tale proposizione:
  $Sn = \sum{k=1}^n k$ è in $\Theta(n^2)$

  • Anche in questa dimostrazione, riscriviamo nuovamente la sommatoria in forma estesa, ma anche in forma invertita:
    $Sn = 1 + 2 + 3 + … + (n − 2) + (n − 1) + n$ $Sn = n + (n − 1) + (n − 2) + … + 3 + 2 + 1$

  • Sommando $Sn$ con se stessa, otteniamo il seguente risultato: $Sn$ 1 2 3 …… n − 2 n − 1 n
    $Sn$ n n − 1 n − 2 …… 3 2 1 $2Sn$ n + 1 n + 1 n + 1 …… n + 1 n + 1 n + 1
    Dunque,
    $2S_n = (n + 1) + (n + 1) + … + (n + 1) + (n + 1) = n(n + 1)$

  • A questo punto, ci basta sfruttare alcune proprietà algebriche
    $2Sn = n(n + 1)$ $Sn = \frac{n(n + 1)}{2} = \frac{n^2 + n}{2} = \Theta(n^2)$

• Dimostrare la seguente proposizione
  $Sn = \sum{k=0}^n 2^k$ è in $\Theta(2^n)$

  • Riscriviamo la somma in forma estesa per poi moltiplicarla per 2
    $Sn = 1 + 2 +2^2 + 2^3 + … + 2^{n-1} + 2^n$ $2 \cdot Sn = 2 \cdot (1 + 2 +2^2 + 2^3 + … + 2^{n-1} + 2^n)$
    $2S_n = 2 + 2^2 + 2^3 + 2^4 + … + 2^n + 2^{n+1}$

  • Gli unici termini non condivisi tra $Sn$ e $2Sn$ sono 1 e $2^{n+1}$
    $2Sn = 2 + 2^2 + 2^3 + 2^4 + … + 2^n + 2^{n+1}$ $Sn = 1 + 2 + 2^2 + 2^3 + … + 2^n$

  • Dunque otteniamo che
    $Sn= 2Sn − S_n = 2^{n+1} − 1$

  • A questo punto calcoliamo il limite asintotico del risultato
    $S_n = 2^{n+1} − 1 = 2^n \cdot 2 − 1 = \Theta(2^n) + \Theta(−1) = \Theta(2^n)$

• Dimostrare la seguente proposizione
  $\sum_{k=1}^n k \cdot 2^k$ è in $\Theta(n \cdot 2^n)$

  • Riscriviamo in forma estesa e moltiplichiamo per 2
    $Sn = 2^1 + 2 \cdot 2^2 + 3 \cdot 2^3 + … + (n − 1) \cdot 2^{n−1} + n \cdot 2^n$ $2Sn = 2^2 + 2 \cdot 2^3 + 3 \cdot 2^4 + … + (n − 1) \cdot 2^n + n \cdot 2^{n+1}$

  • Effettuiamo qualche passaggio algebrico
    $Sn = 2Sn − Sn = −2^1 − 2^2 − 2^3 − 2^4 − … − 2^{n−1} + n \cdot 2^{n+1}$ $−Sn = −(−2^1 − 2^2 − 2^3 − 2^4 − … − 2^n + n \cdot 2^{n+1})$
    $−S_n = 2^1 + 2^2 + 2^3 + 2^4 + … + 2^n − n \cdot 2^{n+1}$

  • A questo punto, è necessario ricordarsi che nella dimostrazione precedente abbiamo ottenuto che
    $\sum{k=0}^n 2^k = 1 + 2^1 + 2^2 + 2^3 + 2^4 + … + 2^n = 2^{n+1} − 1$ dunque, possiamo riscrivere $−Sn$ come $−Sn = 2^1+2^2+2^3+2^4+…+2^n−n\cdot2^{n+1} = (\sum{k=0}^n 2^k)−1−n\cdot2^{n+1}$ $= 2^{n+1}−2−n\cdot2^{n+1}$ per poi calcolare $Sn$
    $−(−S_n) = −(2^{n+1} − 2 − n \cdot 2^{n+1})$
    $= −2^{n+1} + 2 + n \cdot 2^{n+1}$

  • Infine, calcoliamo il limite asintotico del risultato
    $S_n = −2^{n+1} + 2 + n \cdot 2^{n+1} = \Theta(2^n) + \Theta(2) + \Theta(n \cdot 2^n) = \Theta(n \cdot 2^n)$

• Dimostrare la seguente proposizione
  $\sum_{k=1}^n log(k)$ è in $\Theta(n \cdot log(n))$

  • Riscriviamo la sommatoria in forma estesa in modo da applicare le proprietà dei logaritmi
    $S_n = log(1) + log(2) + log(3) + … + log(n)$
    $= log(1 \cdot 2 \cdot 3 \cdot … \cdot n) = log(n!)$

  • Dunque, ignorando la costante c, verifichiamo l’ipotesi
    $log(n!) \leq n \cdot log(n)$