Notação assintótica: O, Ω e Θ
A notação assintótica descreve como o custo cresce quando n fica grande. Ignora constantes e termos menores. O(g) é limite superior, Ω(g) é limite inferior e Θ(g) é limite justo, ou seja, vale O e Ω ao mesmo tempo. Formalmente, f = O(g) se existem c > 0 e n0 tais que f(n) ≤ c·g(n) para todo n ≥ n0.
f(n) = 3n² + 5n + 2 é Θ(n²), logo também é O(n³), mas não é Θ(n³).
Classes de funções em ordem
As bancas cobram a hierarquia de crescimento: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!. A base do logaritmo não muda a classe, pois log_a n e log_b n diferem só por constante. Já na exponencial a base importa: 3ⁿ cresce mais que 2ⁿ.
2ⁿ⁺¹ = 2·2ⁿ, então é O(2ⁿ); mas 2²ⁿ = 4ⁿ, que não é O(2ⁿ).
Análise de pior caso
A análise de pior caso mede o maior custo entre todas as entradas de tamanho n. Ela dá uma garantia: o algoritmo nunca passa desse limite. Melhor caso e caso médio são análises diferentes. O caso médio depende de uma distribuição de probabilidade das entradas.
Quicksort com pivô fixo tem pior caso Θ(n²) em vetor já ordenado e caso médio Θ(n log n).
Na plataforma, cada ideia vem com uma pergunta de checagem, flashcards para revisar e questões da banca.