A notação big O, o O-zão, foi criada para resolver o problema da comparação de algoritmos.

O problema da comparação

Como eu faço pra medir se o meu programa é mais rápido (ou mais eficiente em uso de memória) que o programa do meu colega? Podemos rodar os dois programas várias vezes, com entradas cada vz maiores, medir quanto tempo gasta (se a variável que queremos medir é o tempo de execução), e fazer uma média. Mas e se o compilador mudar? E se quisermos comparar programas independentemente do computador? E se quisermos medir a eficiência intrínseca do algoritmo?

Para isso foram inventadas as notações assintóticas: big-Omega, big-Theta e big-O: limite inferior, limite superior e os dois ao mesmo tempo. Essas notações assintóticas descrevem como os algoritmos se composrtam com entradas cada vez maiores, ou seja, respondem à pergunta quando n tende ao infinito, qual o limite inferior do tempo (demora, pelo menos, quanto tempo pra rodar): Ω(n) (omega de n). Da mesma forma, "demora no máximo quanto tempo pra rodar": Θ(n) (theta de n). Por fim, "na média demora quanto?", ou "qual o limite superior e inferior?": O(n).

Qual a aplicação prática disso?

Saber disso te ajuda a entender porque um método que você usou é pior ou melhor que outro. Te ajuda a comparar duas ferramentas. O simples fato de ter estudado como determinar a complexidade de um algoritmo pode te dar a intuição de que "talvez essa não seja a melhor forma de fazer isso 🤔".

Muita gente acha inútil estudar algumas matérias como essa na faculdade, mas são essas matérias que te dão a base para as abstrações que são necessárias no trabalho. E se você não ficou convencido, dou o útlimo algumento: esse tipo de questão cai muito em entrevistas (questões de Estrutura de Dados e Análise de Algoritmos caem muito, no geral). E se os recrutadores esperam que gente saiba é porque algo de importante deve ter.

rodrigombshá 2 anos

A notação big-o é muito mais antiga que a computação e qualquer problema de algoritmos. Ela serve pra análises assintóticas de crescimento de funções.

"In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion."

rafaelbarbosashá 2 anos
O trio Omega, Theta e Big-O foi proposto por Donald Knuth. Verdade que a notação omega e big-O é bem mais antiga (datando do final do século dezenove), mas o trio e a definição utilizada atualmente em computação é algo bem mais novo: > "the 1970s the big O was popularized in computer science by Donald Knuth, who introduced the related Theta notation, and proposed a different definition for the Omega notation."