Complessità temporale e spaziale

Complessità temporale:

• Caso migliore: O(n)
  • Quando l’array è già ordinato, Insertion Sort esegue un solo passaggio per confermare l’ordine.
• Caso medio e peggiore: O(n²)
  • Nei casi medio e peggiore, richiede un tempo quadratico perché, per ogni elemento, potrebbe essere necessario confrontare e spostare gli elementi di tutta la porzione ordinata.

Complessità spaziale:

• O(1)
  • Insertion Sort è un algoritmo «in-place», cioè non richiede memoria aggiuntiva proporzionale alla dimensione dell’input.
  • Lo spazio utilizzato per l’ordinamento rimane costante, indipendentemente dalla dimensione dell’input.

Riepilogo:

• Insertion Sort è efficiente per insiemi di dati piccoli o array quasi ordinati.
• È meno adatto a insiemi di dati grandi a causa della sua complessità temporale quadratica.
• La complessità spaziale è costante, il che lo rende efficiente in termini di memoria per qualsiasi dimensione dell’input.