Dois aspectos importantes: um problema pode, geralmente, ser resolvido por diferentes algoritmos; a existência de um algoritmo não implica, necessariamente, que este problema possa ser resolvido na prática. A análise de algoritmos pode ser definida como o estudo da estimativa de tempo de execução de algoritmos. Considerando a complexidade de algoritmos, assinale a alternativa que mais representa o melhor caso e o pior caso quando associada à complexidade de algoritmos.

Em análise de complexidade, melhor caso é o menor tempo (ordem de crescimento) que um algoritmo pode levar para uma entrada de tamanho $n$, e pior caso é o maior tempo que ele pode levar para alguma entrada de tamanho $n$.

Assim, para um mesmo algoritmo, é possível que melhor e pior caso sejam diferentes (por exemplo, melhor $O(n)$ e pior $O(n^2)$), ou que sejam iguais quando o comportamento do algoritmo independe da ordem/forma da entrada (ou quando o algoritmo sempre executa essencialmente a mesma quantidade de passos).

Analisando as alternativas:

• (A) usa $O(R\*\log n)$ no “pior caso”, mas R não é um parâmetro padrão do tamanho da entrada (fica incoerente para comparação direta com melhor caso em função de $n$).
• (B) diz melhor $O(n^3)$ e pior $O(n^2)$: impossível, pois o melhor caso não pode ser assintoticamente maior que o pior caso.
• (C) diz melhor $O(n\log n)$ e pior $O(\log n)$: também impossível pelo mesmo motivo.
• (E) melhor $O(n^2\*n^3)=O(n^5)$ e pior $O(n^2)$: novamente impossível.
• (D) melhor $O(n^2)$ e pior $O(n^2)$: é consistente (há algoritmos cujo melhor e pior caso têm a mesma ordem, por exemplo, certos algoritmos de ordenação como selection sort/insertion sort em algumas variações, ou algoritmos com laços sempre completos).

Logo, a alternativa que melhor representa uma associação correta entre melhor e pior caso (sem violar a relação melhor \le pior) é a que coloca ambos como $O(n^2)$.

Alternativa correta: (D).