Uma dúvida frequente que as pessoas têm sobre análise de complexidade é: Para que serve isso? O objetivo da análise de algoritmos é predizer o comportamento de um dado algoritmo. Quando se trata de análise de complexidade, o objetivo é predizer o tempo de execução do algoritmo ou seu consumo de memória, sem ter que implementá-lo e executá-lo em um computador específico.
Vejamos um exemplo. Gostaríamos de comparar dois algoritmos que calculam a soma $s$ dos $n$ primeiros números inteiros, ou seja: $s = 1 + 2 + 3 + \dots + n - 1 + n$.
Operações como as descritas acima são chamadas de operações primitivas. Elas são operações consideradas como tendo custo computacional desprezível.
O livro "Algorithms Illuminated", do professor Tim Roughgarden, traz uma explicação importante sobre operações primitivas. Intuitivamente, uma operação primitiva é um comando ou sentença que realiza uma tarefa simples (adição, multiplicação, comparação, etc.) em variáveis simples (números ou caracteres, por exemplo). Entretanto, em algumas linguagens de programação, uma única linha de código, que a princípio poderia parecer uma operação primitiva, pode realizar um número elevado de operações. Por exemplo, uma linha de código que soma todos os elementos de um arranjo não é uma operaão primitiva. Essa soma possui, na verdade, complexidade linear no tamanho do arranjo, ou seja, é O(n). É importante ficar atento a esses detalhes ao analisar a complexidade de um algoritmo implementado em uma linguagem de programação.
Tendo estabelecido as regras acima, podemos concluir que o algoritmo_b executa cerca de $n$ operações (uma operação para cada elemento $i$ no intervalo $[1,n]$ gerado pela função range(). Matematicamente, dizemos que ele executa $\sim n$ operações. Note que usamos o sinal $\sim$ para indicar aproximadamente (ou cerca de). Expressamos o tempo de execução do algoritmo como uma função de $n$, o tamanho da entrada, porque desejamos predizer o comportamento do algoritmo à medida em que o tamanho da entrada cresce.
A análise do algoritmo_a é um pouco mais complicada, mas nos permitirá concluir que ele executa $\sim n^2$ operações. Isso fica mais claro se analisarmos quantas operações são executadas para cada valor de i. Vejamos:
Tabela 1. Quantidade de operações
[3, n]
[n - 1, n]
Se analisarmos atentamente os valores da tabela acima, veremos que são executadas $1 + 2 + 3 + \dots + n - 1 + n$ operações. Pode parecer difícil determinar o resultado dessa soma, mas felizmente existe uma fórmula para calcular o resultado. Essa fórmula nos diz que:
$1 + 2 + 3 + \dots + n - 1 + n = \frac{n \times (n - 1)}{2} = \frac{n^2 - n}{2}$
Se simplificarmos a fórmula acima, veremos que o algoritmo_a executa $\sim n^2$ operações.
Perceba que para chegar no valor acima nós ignoramos as constantes e termos menores que $n^2$ na fórmula. Essa é outra simplificação importante feita quando estamos analisando a complexidade de um algoritmo: não consideramos constantes (o 2 da fórmula, por exemplo) ou termos menores (como o $n - 1$) no cálculo do número de operações.
Assim, se descobrirmos que um dado algoritmo executa $2n^2 + 50n$ operações, podemos ignorar as constantes e termos de menor ordem e dizer que ele executa $\sim n^2$ operações. Da mesma forma, se um algoritmo realiza $100n$ operações, dizemos simplesmente que ele executa $\sim n$ operações.
Você pode estar se perguntando: "Ora, se temos a fórmula para o cálculo da soma dos $n$ primeiros números inteiros, não podemos simplesmente transformar essa soma em um algoritmo mais eficiente que os dois mostrados anteriormente?" A resposta é: sim, podemos. O algoritmo, que chamaremos de algoritmo_c, possui complexidade constante. Ele pode ser implementado assim:
resultado = algoritmo_c(11)
Você deve ter percebido que invocamos a função algoritmo_c() passando o númeor 11 como parâmetro, embora nosso desejo é calcular a soma dos 10 primeiros números inteiros, ou seja, dos números de 1 a 10 (inclusive). Tivemos que passar 11 como parâmetro porque a fórmula, do modo como a usamos, começa a contar os números a partir de zero, totalizando 11 números, portanto. Outra alternativa seria usarmos a fórmula $\frac{n \times (n + 1)}{2}$, passando 10 como parâmetro.
Em suma, quando estiver analisando a complexidade assintótica de um algoritmo, descarte fatores contantes e termos de menor ordem, pois fatores constantes dependem muito do sistema (hardware ou arquitetura) e termos de menor ordem são irrelevantes para entradas grandes.