შესაძლებელია უფრო სწრაფი გადაწყვეტილების მოძებნა, ვიდრე 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²), սակայն կոնկրետ պատասխանն առաջադրանքի և նրա սահմանափակումների վրա է կախված։