Πώς γράφεται η αλγοριθμική πολυπλοκότητα; Ποια είναι η πολυπλοκότητα της ταξινόμησης με φούσκα; Ποια είναι η πολυπλοκότητα της γρήγορης ταξινόμησης;

Η αλγοριθμική πολυπλοκότητα συνήθως γράφεται σε σημειωτική Big O, που περιγράφει την ασυμπτωτική εκτίμηση του χρόνου εκτέλεσης ή της χρήσης μνήμης από τον αλγόριθμο ανάλογα με το μέγεθος των εισερχόμενων δεδομένων.

• Ταξινόμηση με φυσαλίδα έχει πολυπλοκότητα O(n²) στις χειρότερες και μέσες περιπτώσεις, καθώς κάθε στοιχείο συγκρίνεται με κάθε άλλο.

• Γρήγορη ταξινόμηση λειτουργεί κατά μέσο όρο σε O(n log n), αλλά στην χειρότερη περίπτωση (π.χ., όταν ο πίνακας είναι ήδη ταξινομημένος και επιλέγεται κακός πυρήνας) μπορεί να υποβαθμιστεί σε O(n²).

Παράδειγμα καταγραφής:

Ταξινόμηση με φυσαλίδα: O(n^2)
Γρήγορη ταξινόμηση: O(n log n) κατά μέσο όρο, O(n^2) στην χειρότερη περίπτωση