Μπορεί να βρεθεί λύση πιο γρήγορα από το O(n^2);

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

Αν ένας αλγόριθμος με τετραγωνική πολυπλοκότητα προκύπτει λόγω της ανάγκης να συγκριθούν όλα τα ζεύγη στοιχείων (π.χ. αναζήτηση διπλοτύπων, σύγκριση όλων των ζευγών), τότε συχνά υπάρχουν πιο αποδοτικές προσεγγίσεις:

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

Ωστόσο, για ορισμένα προβλήματα, η τετραγωνική πολυπλοκότητα αποτελεί το κατώτατο όριο λόγω της φύσης του προβλήματος.

Παράδειγμα: αναζήτηση ζευγών με δεδομένο άθροισμα σε έναν πίνακα.

Τετραγωνική λύση:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            // βρέθηκε ζευγάρι
        }
    }
}

Πιο αποδοτική λύση με χρήση πίνακα κατακερματισμού — O(n):

Set<Integer> complements = new HashSet<>();
for (int num : arr) {
    if (complements.contains(num)) {
        // βρέθηκε ζευγάρι
    } else {
        complements.add(target - num);
    }
}

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