É possível encontrar uma solução mais rápida do que O(n^2)?

A questão de saber se é possível encontrar uma solução mais rápida que O(n²) depende da tarefa específica e da sua estrutura.

Se um algoritmo com complexidade quadrática surge devido à necessidade de comparar todos os pares de elementos (por exemplo, procura de duplicados, comparação de todos os pares), muitas vezes existem abordagens mais eficientes:

• Uso de estruturas de dados adicionais (tabelas de hash, conjuntos) para reduzir o tempo de procura para O(n).
• Aplicação de ordenação seguida de uma passagem linear, o que dá O(n log n).
• Uso de algoritmos especializados, por exemplo, algoritmos baseados em programação dinâmica, métodos gananciosos ou divide e conquista.

No entanto, para algumas tarefas, a complexidade quadrática é o limite inferior devido à natureza do problema.

Exemplo: procura de pares com uma soma dada num array.

Solução quadrática:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            // par encontrado
        }
    }
}

Solução mais eficiente usando uma tabela hash — O(n):

Set<Integer> complements = new HashSet<>();
for (int num : arr) {
    if (complements.contains(num)) {
        // par encontrado
    } else {
        complements.add(target - num);
    }
}

Assim, muitas vezes é possível encontrar uma solução mais rápida que O(n²), mas a resposta concreta depende da tarefa e das suas restrições.