Regra do Coeficiente: “Livre-se das Constantes”

Vamos rever a regra do coeficiente. Essa regra é a mais fácil de entender. Simplesmente necessita que você ignore qualquer tamanho de entrada de dados das constantes.

Coeficientes no Big-O são insignificantes. Além disso, a regra mais importante do Big-O são as notações.

Se f(n) é O(g(n)), então kf(n) é O(g(n)), para qualquer constante k>0.

Isto significa que ambos 5f(n) e f(n) tem a mesma notação de Big-O de O(f(n)). Um exemplo de código com a complexidade de O(n):

function a(n){

            var count = 0;

            for(var i = 0; i < n; i++){

                        count+=1;

            }

            return count;

}

Esse bloco de código tem f(n) = n. Isto adiciona uma contagem de n vezes. Além disso, essa função é O(n) de complexidade:

function a(n){

            var count = 0;

            for(var i = 0; i < 5*n; i++){

                        count+=1;

            }

            return count;

}

Esse bloco tem f(n) = 5n. Isto porque executa do 0 ao 5n. Contudo, os dois exemplos ambos têm a notação Big-O de O(n).

Simplesmente, porque se n é infinito ou qualquer outro número, as quatros operações adicionais são tem significados.

Isto vai ter uma execução de n vezes. Quaisquer constantes são insignificantes na notação Big-O.

O código a seguir apresenta uma outra função com uma complexidade linear com uma operação adicional na linha 6.

Esse bloco de código tem f(n) = n+1. Há um +3 na última operação (count+=3). Isto ainda tem a notação O(n) do Big-O.

Isto porque a operação + 3 não depende da entrada n. Como n pode ser infinito, ela se torna insignificante.

Regra da Soma: “Eleve os Big-OS”

A regra da soma é intuitiva de entender, complexidade temporal pode ser adicionada.

Imagine um mestre de algoritmo que envolve outros dois algoritmos. A notação Big-O deste mestre do algoritmo é simplesmente a soma das outras duas notações Big-O.

Se f(n) é O(h(n)) e g(n) é O(p(n)), então f(n)+g(n) é O(h(n)+p(n)).

É importante lembrar de aplicar a regra do coeficiente depois de aplicar esta regra.

Segue um código que apresenta uma função com dois loops onde suas complexidades devem ser consideradas independentes e então somadas:

Nesse exemplo, a linha 4 tem um f(n)=n e na linha 7 tem um f(n)=5n. Isso resulta em 6n.

Contudo, quando aplicada a regra do coeficiente, o resultado é O(n) = n.