O que é uma explicação simples em inglês da notação “Big O”?

Eu prefiro a menor definição formal possível e matemática simples.

Nota rápida, isso é quase certamente confundir notação Big O (que é um limite superior) com notação Theta (que é um limite de dois lados). Na minha experiência, isso é realmente típico de discussões em contextos não acadêmicos. Desculpas por qualquer confusão causada.


A complexidade do Big O pode ser visualizada com este gráfico:

Big O Analysis

A definição mais simples que posso dar para a notação Big-O é esta:

A notação Big-O é uma representação relativa da complexidade de um algoritmo.

Há algumas palavras importantes e deliberadamente escolhidas nessa frase:

  • parente: você só pode comparar maçãs com maçãs. Você não pode comparar um algoritmo para fazer multiplicação aritmética a um algoritmo que classifica uma lista de inteiros. Mas uma comparação de dois algoritmos para fazer operações aritméticas (uma multiplicação, uma adição) lhe dirá algo significativo;
  • representação: Big-O (na sua forma mais simples) reduz a comparação entre algoritmos para uma única variável. Essa variável é escolhida com base em observações ou suposições. Por exemplo, algoritmos de ordenação são tipicamente comparados com base em operações de comparação (comparando dois nós para determinar sua ordem relativa). Isso pressupõe que a comparação é cara. Mas e se a comparação for barata, mas a troca é cara? Isso muda a comparação; e
  • complexidade: se eu demorar um segundo para classificar 10.000 elementos, quanto tempo levarei para classificar um milhão? Complexidade, neste caso, é uma medida relativa a outra coisa.

Volte e releia o texto acima quando você leu o resto.

O melhor exemplo de Big-O que consigo pensar é em fazer aritmética. Pegue dois números (123456 e 789012). As operações aritméticas básicas que aprendemos na escola foram:

  • Adição;
  • subtração;
  • multiplicação; e
  • divisão.

Cada um deles é uma operação ou um problema. Um método para resolvê-los é chamado de algoritmo .

A adição é a mais simples. Você alinha os números para cima (à direita) e adiciona os dígitos em uma coluna escrevendo o último número dessa adição no resultado. A parte ‘dez’ desse número é transportada para a próxima coluna.

Vamos supor que a adição desses números seja a operação mais cara nesse algoritmo. É lógico que, para sumr esses dois números, temos que sumr 6 dígitos (e possivelmente carregar um sétimo). Se sumrmos dois números de 100 dígitos juntos, teremos que fazer 100 adições. Se adicionarmos dois números de 10.000 dígitos, temos que fazer 10.000 adições.

Veja o padrão? A complexidade (sendo o número de operações) é diretamente proporcional ao número de dígitos n no maior número. Chamamos isso de O (n) ou complexidade linear .

A subtração é semelhante (exceto que você pode precisar pedir emprestado em vez de carregar).

A multiplicação é diferente. Você alinha os números, pega o primeiro dígito no número inferior e multiplica-o um contra o outro no número do topo, e assim sucessivamente através de cada dígito. Então, para multiplicar nossos dois números de 6 dígitos, devemos fazer 36 multiplicações. Podemos precisar fazer até 10 ou 11 colunas para obter o resultado final também.

Se tivermos dois números de 100 dígitos, precisaremos de 10.000 multiplicações e 200 acréscimos. Para dois números de um milhão de dígitos, precisamos fazer um trilhão (10 12 ) de multiplicações e dois milhões de acréscimos.

Como o algoritmo escala com n- quadrado , isso é O (n 2 ) ou complexidade quadrática . Este é um bom momento para apresentar outro conceito importante:

Nós só nos preocupamos com a parte mais significativa da complexidade.

O astuto pode ter percebido que poderíamos expressar o número de operações como: n 2 + 2n. Mas como você viu em nosso exemplo com dois números de um milhão de dígitos cada, o segundo termo (2n) se torna insignificante (respondendo por 0,0002% do total de operações naquele estágio).

Pode-se notar que assumimos o pior cenário aqui. Ao multiplicar números de 6 dígitos, se um deles é de 4 dígitos e o outro é de 6 dígitos, então temos apenas 24 multiplicações. Ainda assim, calculamos o pior cenário possível para aquele ‘n’, ou seja, quando ambos são números de 6 dígitos. Portanto, a notação Big-O é sobre o pior cenário de um algoritmo

A lista telefônica

O próximo melhor exemplo que posso imaginar é o catálogo telefônico, normalmente chamado de Páginas Brancas ou similar, mas varia de país para país. Mas eu estou falando sobre o que lista as pessoas pelo sobrenome e, em seguida, as iniciais ou o primeiro nome, possivelmente o endereço e, em seguida, os números de telefone.

Agora, se você estivesse instruindo um computador a procurar o número de telefone de “John Smith” em uma lista telefônica que contém 1.000.000 de nomes, o que você faria? Ignorando o fato de que você poderia adivinhar até onde os S’s começaram (vamos supor que você não pode), o que você faria?

Uma implementação típica pode ser abrir para o meio, pegar os 500.000 e comparar com “Smith”. Se acontecer de ser “Smith, John”, nós tivemos muita sorte. Muito mais provável é que “John Smith” será antes ou depois desse nome. Se for depois, dividimos a última metade da lista telefônica pela metade e repetimos. Se é antes disso, dividimos a primeira metade da lista telefônica ao meio e repetimos. E assim por diante.

Isso é chamado de pesquisa binária e é usado todos os dias na programação, quer você perceba ou não.

Então, se você quiser encontrar um nome em uma lista telefônica de um milhão de nomes, você pode realmente encontrar qualquer nome, fazendo isso no máximo 20 vezes. Ao comparar algoritmos de busca, decidimos que essa comparação é nossa ‘n’.

  • Para uma lista telefónica de 3 nomes, são necessárias 2 comparações (no máximo).
  • Para 7, leva no máximo 3.
  • Por 15 demora 4.
  • Para 1.000.000 leva 20.

Isso é incrivelmente bom, não é?

Nos termos Big-O, isso é O (log n) ou complexidade logarítmica . Agora o logaritmo em questão poderia ser ln (base e), log 10 , log 2 ou alguma outra base. Não importa que ainda seja O (log n) assim como O (2n 2 ) e O (100n 2 ) ainda são ambos O (n 2 ).

Vale a pena explicar que o Big O pode ser usado para determinar três casos com um algoritmo:

  • Melhor caso: Na pesquisa por catálogo telefônico, o melhor caso é que encontramos o nome em uma comparação. Isso é O (1) ou complexidade constante ;
  • Caso esperado: Como discutido acima, este é O (log n); e
  • Pior caso: Isso também é O (log n).

Normalmente, não nos importamos com o melhor caso. Estamos interessados ​​no esperado e pior caso. Às vezes, um ou outro deles será mais importante.

De volta à lista telefônica.

E se você tiver um número de telefone e quiser encontrar um nome? A polícia tem uma lista telefônica invertida, mas tais consultas são negadas ao público em geral. Ou são eles? Tecnicamente, você pode inverter a pesquisa de um número em uma lista telefônica comum. Como?

Você começa pelo primeiro nome e compara o número. Se é um jogo, ótimo, se não, você passa para o próximo. Você tem que fazer desta forma porque a lista telefônica não é ordenada (pelo número de telefone de qualquer maneira).

Então, para encontrar um nome dado o número de telefone (pesquisa inversa):

  • Melhor Caso: O (1);
  • Caso esperado: O (n) (para 500.000); e
  • Pior caso: O (n) (para 1.000.000).

O vendedor ambulante

Este é um problema bastante famoso na ciência da computação e merece uma menção. Neste problema você tem N cidades. Cada uma dessas cidades está ligada a uma ou mais outras cidades por uma estrada de certa distância. O problema do vendedor ambulante é encontrar o passeio mais curto que visita todas as cidades.

Soa simples? Pense de novo.

Se você tem 3 cidades A, B e C com estradas entre todos os pares, então você pode ir:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Bem, na verdade, há menos que isso, porque alguns deles são equivalentes (A → B → C e C → B → A são equivalentes, por exemplo, porque eles usam as mesmas estradas, apenas no sentido inverso).

Na realidade existem 3 possibilidades.

  • Leve isso para 4 cidades e você terá (iirc) 12 possibilidades.
  • Com 5 é 60.
  • 6 torna-se 360.

Esta é uma function de uma operação matemática chamada fatorial . Basicamente:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 10 64

Portanto, o Big-O do problema do Salesman Traveling é O (n!) Ou complexidade fatorial ou combinatória .

Quando você chega a 200 cidades, não há tempo suficiente no universo para resolver o problema com computadores tradicionais.

Algo para pensar sobre.

Horário Polinomial

Outro ponto que gostaria de mencionar é que qualquer algoritmo que tem uma complexidade de O (n a ) é dito ter complexidade polinomial ou é solucionável em tempo polinomial .

O (n), O (n 2 ) etc são todos tempo polinomial. Alguns problemas não podem ser resolvidos em tempo polinomial. Certas coisas são usadas no mundo por causa disso. Criptografia de chave pública é um excelente exemplo. É computacionalmente difícil encontrar dois fatores primos de um número muito grande. Se não fosse, não poderíamos usar os sistemas de chave pública que usamos.

De qualquer forma, é isso para minha explicação (esperançosamente simples, em inglês) de Big O (revisado).

Mostra como um algoritmo é dimensionado.

O (n 2 ) : conhecido como complexidade quadrática

  • 1 item: 1 segundo
  • 10 itens: 100 segundos
  • 100 itens: 10000 segundos

Observe que o número de itens aumenta por um fator de 10, mas o tempo aumenta por um fator de 10 2 . Basicamente, n = 10 e assim O (n 2 ) nos dá o fator de escala n 2 que é 10 2 .

O (n) : conhecido como complexidade linear

  • 1 item: 1 segundo
  • 10 itens: 10 segundos
  • 100 itens: 100 segundos

Desta vez, o número de itens aumenta por um fator de 10 e o mesmo acontece com o tempo. n = 10 e, portanto, o fator de escala de O (n) é 10.

O (1) : conhecido como complexidade constante

  • 1 item: 1 segundo
  • 10 itens: 1 segundo
  • 100 itens: 1 segundo

O número de itens ainda está aumentando por um fator de 10, mas o fator de escala de O (1) é sempre 1.

O (log n) : conhecido como complexidade logarítmica

  • 1 item: 1 segundo
  • 10 itens: 2 segundos
  • 100 itens: 3 segundos
  • 1000 itens: 4 segundos
  • 10000 itens: 5 segundos

O número de cálculos é aumentado apenas por um log do valor de input. Portanto, neste caso, assumindo que cada cálculo leva 1 segundo, o log da input n é o tempo necessário, portanto log n .

Essa é a essência disso. Eles reduzem a matemática para baixo, então pode não ser exatamente n2 ou o que quer que seja, mas esse será o fator dominante no escalonamento.

A notação Big-O (também chamada de notação “crescimento assintótico”) é o que as funções “parecem” quando você ignora fatores constantes e coisas próximas à origem . Eu uso isto para falar sobre como uma coisa escala .


Noções básicas

para inputs “suficientemente” grandes …

  • f(x) ∈ O(upperbound) significa que “não cresce mais rápido que” de upperbound
  • f(x) ∈ Ɵ(justlikethis) significa f “cresce exatamente como” justlikethis
  • f(x) ∈ Ω(lowerbound) significa que “não cresce mais devagar do que” para lowerbound

A notação big-O não se preocupa com fatores constantes: diz-se que a function 9x² “cresce exatamente como” 10x² . Nem a notação assintótica big-O se preocupa com coisas não assintóticas (“coisas próximas à origem” ou “o que acontece quando o tamanho do problema é pequeno”): a function 10x² é dita “crescer exatamente como” 10x² - x + 2 .

Por que você iria querer ignorar as partes menores da equação? Porque eles se tornam completamente diminuídos pelas grandes partes da equação quando você considera escalas maiores e maiores; sua contribuição se torna anã e irrelevante. (Veja a seção de exemplo.)

Dito de outra forma, é tudo sobre a proporção que você vai para o infinito. Se você dividir o tempo real que leva o O(...) , você terá um fator constante no limite de grandes inputs. Intuitivamente isso faz sentido: as funções “escalam como” uma a outra se você puder multiplicar uma para obter a outra. Isto é, quando dizemos …

 actualAlgorithmTime(N) ∈ O(bound(N)) eg "time to mergesort N elements is O(N log(N))" 

… isto significa que para tamanhos de problema “grande o suficiente” N (se ignorarmos coisas perto da origem), existe alguma constante (por exemplo, 2.5, completamente inventada) tal que:

 actualAlgorithmTime(N) eg "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N) 

Existem muitas opções de constante; muitas vezes a "melhor" escolha é conhecida como "fator constante" do algoritmo ... mas muitas vezes a ignoramos como se ignorássemos termos não maiores (consulte a seção "Fatores constantes" para saber por que eles geralmente não importam). Você também pode pensar na equação acima como um limite, dizendo " Na pior das hipóteses, o tempo que leva nunca será pior do que aproximadamente N*log(N) , dentro de um fator de 2,5 (um fator constante que don ' se importam muito) ".

Em geral, O(...) é o mais útil porque geralmente nos preocupamos com o comportamento de pior caso. Se f(x) representa algo "ruim" como processador ou uso de memory, então " f(x) ∈ O(upperbound) " significa " upperbound é o pior cenário do uso do processador / memory".


Aplicações

Como uma construção puramente matemática, a notação big-O não se limita a falar sobre o tempo de processamento e a memory. Você pode usá-lo para discutir as assintóticas de qualquer coisa em que o dimensionamento seja significativo, como:

  • o número de possíveis apertos de mão entre N pessoas em uma festa ( Ɵ(N²) , especificamente N(N-1)/2 , mas o que importa é que "escala como" )
  • número probabilístico esperado de pessoas que viram algum marketing viral em function do tempo
  • como a latência do website é dimensionada com o número de unidades de processamento em uma CPU ou GPU ou cluster de computador
  • como as escalas de saída de calor na CPU morrem em function da contagem de transistores, tensão, etc.
  • quanto tempo um algoritmo precisa executar, como uma function do tamanho da input
  • quanto espaço um algoritmo precisa executar, como uma function do tamanho da input

Exemplo

Para o exemplo de handshake acima, todos em uma sala sacodem a mão de todos. Nesse exemplo, #handshakes ∈ Ɵ(N²) . Por quê?

Volte um pouco para cima: o número de apertos de mão é exatamente n-choose-2 ou N*(N-1)/2 (cada um dos N pessoas aperta as mãos de N-1 outras pessoas, mas isso duplica os handshakes 2):

todos apertam todos os outros. Crédito de imagem e licença por wikipedia / wikimedia commons matriz de adjacência

No entanto, para números muito grandes de pessoas, o termo linear N é pequeno e efetivamente contribui com 0 para a proporção (no gráfico: a fração de checkboxs vazias na diagonal sobre checkboxs totais diminui à medida que o número de participantes se torna maior). Portanto, o comportamento de escala é order N² , ou o número de apertos de mão "cresce como o N²".

 #handshakes(N) ────────────── ≈ 1/2 N² 

É como se as checkboxs vazias na diagonal do gráfico (N * (N-1) / 2 marcas de verificação) não estivessem lá (marcas de verificação N 2 assintoticamente).

(digressão temporária de "plain inglês" 🙂 Se você quisesse provar isso para si mesmo, você poderia executar alguma simples álgebra na proporção para dividi-la em vários termos ( lim significa "considerado no limite de", apenas ignorá-lo se você não viu, é apenas notação para "e N é realmente muito grande"):

  N²/2 - N/2 (N²)/2 N/2 1/2 lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2 N→∞ N² N→∞ N² N² N→∞ 1 ┕━━━┙ this is 0 in the limit of N→∞: graph it, or plug in a really large number for N 

tl: dr: O número de apertos de mão "parece tanto" x² para valores grandes, que, se fôssemos escrever a proporção # apertos de mão / x², o fato de não precisarmos exatamente de x2 apertos de mão nem apareceria no decimal por um tempo arbitrariamente grande.

por exemplo, para x = 1 milhão, proporção # apertos de mão / x²: 0,499999 ...


Construindo a Intuição

Isso nos permite fazer declarações como ...

"Para insumos grandes o suficiente = N, não importa qual seja o fator constante, se eu duplicar o tamanho da input ...

  • ... Eu dobro o tempo que um algoritmo O (N) ("tempo linear") leva. "

    N → (2N) = 2 ( N )

  • ... Eu dobro-quadrado (quadruplicar) o tempo que um algoritmo O (N²) ("tempo quadrático") leva. " (Por exemplo, um problema 100x tão grande leva 100² = 10000x contanto ... possivelmente insustentável)

    → (2N) ² = 4 ( )

  • ... Eu duplamente cúbico (octuple) o tempo que um algoritmo O (N³) ("tempo cúbico") toma. " (Eg um problema 100x tão grande leva 100³ = 1000000x quanto tempo ... muito insustentável)

    cN³ → c (2N) ³ = 8 ( cN³ )

  • ... Eu adiciono um valor fixo ao tempo que um algoritmo O (log (N)) ("tempo logarítmico") toma. " (Barato!)

    log (N) → log (2N) = (log (2)) + ( log (N) ) = (quantidade fixa) + ( log c (N) )

  • ... Eu não mudo o tempo que um algoritmo O (1) ("tempo constante") toma. " (O mais barato!)

    c * 1c * 1

  • ... Eu "(basicamente) dobro" o tempo que um algoritmo O (N log (N)) leva. " (Bastante comum)

    é menor que O (N 1.000001 ), o que você pode estar disposto a chamar de basicamente linear

  • ... Eu aumento ridiculamente o tempo que um algoritmo O (2 N ) ("tempo exponencial") leva. " (Você dobraria (ou triplicaria, etc.) o tempo apenas aumentando o problema por uma única unidade)

    2 N → 2 2N = (4 N ) ............ por outro lado ...... 2 N → 2 N + 1 = 2 N 2 1 = 2 2 N

[para o matematicamente inclinado, você pode passar o mouse sobre os spoilers para sidenotes menores]

(com crédito para https://stackoverflow.com/a/487292/711085 )

(Tecnicamente, o fator constante talvez pudesse importar em alguns exemplos mais esotéricos, mas eu expressei as coisas acima (por exemplo, em log (N)) de tal forma que isso não acontece)

Essas são as ordens de crescimento que os programadores e os cientistas da computação aplicados usam como pontos de referência. Eles veem isso o tempo todo. (Então, enquanto você poderia tecnicamente pensar "dobrar a input faz um algoritmo O (√N) 1.414 vezes mais lento", é melhor pensar nisso como "isso é pior que logarítmico, mas melhor que linear".)


Fatores constantes

Normalmente, não nos importamos com os fatores constantes específicos, porque eles não afetam a maneira como a function cresce. Por exemplo, dois algoritmos podem levar o tempo O(N) para completar, mas um pode ser duas vezes mais lento que o outro. Normalmente, não nos importamos muito, a menos que o fator seja muito grande, pois otimizar é um negócio complicado ( quando a otimização é prematura? ); também o mero ato de escolher um algoritmo com um grande-O melhor freqüentemente melhorará o desempenho em ordens de grandeza.

Alguns algoritmos assintoticamente superiores (por exemplo, uma sorting O(N log(log(N))) podem ter um fator constante tão grande (por exemplo, 100000*N log(log(N)) ), ou sobrecarga que é relativamente grande como O(N log(log(N))) com um oculto + 100*N , que raramente valem a pena usar mesmo em "big data".


Por que O (N) às vezes é o melhor que você pode fazer, ou seja, por que precisamos de estruturas de dados

O(N) algoritmos O(N) são, em certo sentido, os "melhores" algoritmos, se você precisar ler todos os seus dados. O próprio ato de ler um monte de dados é uma operação O(N) . Colocá-lo na memory normalmente é O(N) (ou mais rápido se você tiver suporte de hardware ou nenhum tempo se você já leu os dados). No entanto, se você tocar ou mesmo olhar para cada parte dos dados (ou até mesmo todos os outros dados), seu algoritmo levará o tempo O(N) para executar essa tarefa. Nomatter quanto tempo seu algoritmo real leva, será pelo menos O(N) porque passou esse tempo olhando para todos os dados.

O mesmo pode ser dito para o próprio ato de escrever . Todos os algoritmos que imprimem N coisas levarão N tempo, porque a saída é pelo menos desse tamanho (por exemplo, imprimir todas as permutações (maneiras de reorganizar) um conjunto de N cartas de baralho é fatorial: O(N!) ).

Isso motiva o uso de estruturas de dados : uma estrutura de dados requer a leitura dos dados apenas uma vez (geralmente O(N) tempo), mais alguma quantidade arbitrária de pré-processamento (por exemplo, O(N) ou O(N log(N)) ou O(N²) ) que tentamos manter pequeno. Posteriormente, modificar a estrutura de dados (inserções / exclusões / etc.) e fazer consultas sobre os dados leva muito pouco tempo, como O(1) ou O(log(N)) . Você prossegue para fazer um grande número de consultas! Em geral, quanto mais trabalho você estiver disposto a fazer antes do tempo, menos trabalho você terá que fazer mais tarde.

Por exemplo, digamos que você tenha as coordenadas de latitude e longitude de milhões de segmentos de estradas e queira encontrar todos os cruzamentos de ruas.

  • Método ingênuo: Se você tivesse as coordenadas de um cruzamento de ruas e quisesse examinar as ruas próximas, teria que percorrer os milhões de segmentos de cada vez e verificar cada uma delas quanto a adjacência.
  • Se você só precisasse fazer isso uma vez, não seria um problema ter que fazer o método ingênuo O(N) funcionar apenas uma vez, mas se você quiser fazer isso muitas vezes (neste caso, N vezes, uma vez para cada segmento), teríamos que fazer O(N²) trabalho, ou 1000000² = 1000000000000 operações. Não é bom (um computador moderno pode realizar cerca de um bilhão de operações por segundo).
  • Se usarmos uma estrutura simples chamada tabela de hash (uma tabela de consulta de velocidade instantânea, também conhecida como hashmap ou dictionary), pagamos um pequeno custo pré-processando tudo em tempo O(N) . Posteriormente, leva-se apenas tempo constante, em média, para procurar algo pela sua chave (nesse caso, nossa chave são as coordenadas de latitude e longitude, arredondadas em uma grade; pesquisamos as áreas adjacentes das quais só há 9, que é um constante).
  • Nossa tarefa passou de um O(N²) inviável para um O(N) gerenciável, e tudo o que precisávamos fazer era pagar um custo menor para fazer uma tabela de hash.
  • analogia : A analogia neste caso particular é um quebra-cabeça: Criamos uma estrutura de dados que explora alguma propriedade dos dados. Se nossos segmentos de estrada são como peças de quebra-cabeça, os agrupamos combinando cor e padrão. Em seguida, exploramos isso para evitar fazer trabalhos extras mais tarde (comparando peças de quebra-cabeça de colors semelhantes entre si, não a todas as outras peças de quebra-cabeça).

A moral da história: uma estrutura de dados nos permite acelerar as operações. Estruturas de dados ainda mais avançadas permitem combinar, atrasar ou até mesmo ignorar operações de maneiras incrivelmente inteligentes. Diferentes problemas teriam diferentes analogias, mas todos envolveriam organizar os dados de uma maneira que explora alguma estrutura que nos interessa, ou que artificialmente impusemos a ela para a contabilidade. Nós trabalhamos antes do tempo (basicamente planejando e organizando), e agora as tarefas repetidas são muito mais fáceis!


Exemplo prático: visualizando ordens de crescimento durante a codificação

A notação assintótica é, em sua essência, bastante separada da programação. A notação assintótica é uma estrutura matemática para pensar sobre como as coisas podem ser dimensionadas e pode ser usada em muitos campos diferentes. Dito isto ... é assim que você aplica a notação assintótica à codificação.

Noções básicas: sempre que interagimos com todos os elementos em uma coleção de tamanho A (como um array, um conjunto, todas as chaves de um mapa, etc.), ou executamos A iterações de um loop, que é um fator multiplicativo de tamanho A Por que eu digo "um fator multiplicativo"? - porque loops e funções (quase por definição) têm tempo de execução multiplicativo: o número de iterações, vezes o trabalho feito no loop (ou para funções: o número de vezes que você chama o function, vezes o trabalho feito na function). (Isso vale, se não fizermos nada extravagante, como pular loops ou sair do loop antecipadamente, ou alterar o stream de controle na function com base em argumentos, o que é muito comum.) Aqui estão alguns exemplos de técnicas de visualização, com acompanhamento de pseudocódigo.

(aqui, os x s representam unidades de trabalho em tempo constante, instruções do processador, opcodes do interpretador, etc.)

 for(i=0; i A*1 --> O(A) time visualization: |<------ A ------->| 1 2 3 4 5 xx ... x other languages, multiplying orders of growth: javascript, O(A) time and space someListOfSizeA.map((x,i) => [x,i]) python, O(rows*cols) time and space [[r*c for c in range(cols)] for r in range(rows)] 

Exemplo 2:

 for every x in listOfSizeA: // A x ... some O(1) operation // 1 some O(B) operation // B for every y in listOfSizeC: // C x ... some O(1) operation // 1 --> O(A*(1 + B + C)) O(A*(B+C)) (1 is dwarfed) visualization: |<------ A ------->| 1 xxxxxx ... x 2 xxxxxx ... x ^ 3 xxxxxx ... x | 4 xxxxxx ... x | 5 xxxxxx ... x B <-- A*B xxxxxxx ... x | ................... | xxxxxxx ... xv xxxxxxx ... x ^ xxxxxxx ... x | xxxxxxx ... x | xxxxxxx ... x C <-- A*C xxxxxxx ... x | ................... | xxxxxxx ... xv 

Exemplo 3:

 function nSquaredFunction(n) { total = 0 for i in 1..n: // N x for j in 1..n: // N x total += i*k // 1 return total } // O(n^2) function nCubedFunction(a) { for i in 1..n: // A x print(nSquaredFunction(a)) // A^2 } // O(a^3) 

Se fizermos algo um pouco complicado, você ainda poderá imaginar visualmente o que está acontecendo:

 for x in range(A): for y in range(1..x): simpleOperation(x*y) xxxxxxxxxx | xxxxxxxxx | xxxxxxxx | xxxxxxx | xxxxxx | xxxxx | xxxx | xxx | xx | x___________________| 

Aqui, o menor esboço reconhecível que você pode desenhar é o que importa; um triângulo é uma forma bidimensional (0,5 A ^ 2), assim como um quadrado é uma forma bidimensional (A ^ 2); o fator constante de dois aqui permanece na relação assintótica entre os dois, porém nós o ignoramos como todos os fatores ... (Há algumas nuances infelizes nessa técnica que eu não entro aqui; pode enganar você).

Claro que isso não significa que loops e funções sejam ruins; pelo contrário, eles são os blocos de construção das modernas linguagens de programação, e nós os amamos. No entanto, podemos ver que a forma como tecemos loops e funções e condicionais juntamente com os nossos dados (stream de controle, etc.) imita o tempo e o uso do espaço de nosso programa! Se o uso do tempo e do espaço se torna um problema, é quando recorremos à inteligência e encontramos um algoritmo ou estrutura de dados fácil que não tínhamos considerado para reduzir a ordem de crescimento de alguma forma. No entanto, essas técnicas de visualização (embora nem sempre funcionem) podem lhe dar uma ideia ingênua sobre o pior momento possível.

Aqui está outra coisa que podemos reconhecer visualmente:

 <----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxx xxxx xx x 

Podemos apenas reorganizar isso e ver que é O (N):

 <----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx|xxxxxxxx|xxxx|xx|x 

Ou talvez você registre (N) as passagens dos dados, para o tempo total O (N * log (N)):

  <----------------------------- N -----------------------------> ^ xxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxx | xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx lgN xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx | xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx vx|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x 

Não relacionado, mas vale a pena mencionar novamente: Se executarmos um hash (por exemplo, uma consulta dictionary / hashtable), isso é um fator de O (1). Isso é bem rápido.

 [myDictionary.has(x) for x in listOfSizeA] \----- O(1) ------/ --> A*1 --> O(A) 

Se fizermos algo muito complicado, como com uma function recursiva ou um algoritmo de divisão e conquista, você pode usar o Teorema do Mestre (geralmente funciona) ou, em casos ridículos, o Teorema de Akra-Bazzi (quase sempre funciona) você procura o tempo de execução do seu algoritmo na Wikipedia.

Mas os programadores não pensam assim porque, eventualmente, a intuição do algoritmo acaba se tornando uma segunda natureza. Você começará a codificar algo ineficiente e imediatamente pensar "estou fazendo algo extremamente ineficiente? ". Se a resposta for "sim" E você prevê que realmente importa, então você pode dar um passo para trás e pensar em vários truques para fazer as coisas correrem mais rápido (a resposta é quase sempre "use um hashtable", raramente "use uma tree", e muito raramente algo um pouco mais complicado).


Complexidade amortizada e média de casos

Há também o conceito de "amortizado" e / ou "caso médio" (note que estes são diferentes).

Caso Médio : Não é mais do que usar a notação big-O para o valor esperado de uma function, em vez da própria function. No caso usual em que você considera todas as inputs como igualmente possíveis, o caso médio é apenas a média do tempo de execução. Por exemplo com quicksort, mesmo que o pior caso seja O(N^2) para algumas inputs realmente ruins, o caso médio é o usual O(N log(N)) (as inputs ruins são muito pequenas em número, então poucos que não os notamos no caso médio).

Pior Caso Amortizado : Algumas estruturas de dados podem ter uma complexidade de pior caso que é grande, mas garantir que, se você fizer muitas dessas operações, a quantidade média de trabalho que você faz será melhor do que o pior caso. Por exemplo, você pode ter uma estrutura de dados que normalmente leva tempo O(1) constante. No entanto, ocasionalmente, ele 'soluça' e toma O(N) tempo para uma operação aleatória, porque talvez ele precise fazer alguma contabilidade ou garbage collection ou algo assim ... mas ele promete que se soluçar, não hiccup again for N more operations. The worst-case cost is still O(N) per operation, but the amortized cost over many runs is O(N)/N = O(1) per operation. Because the big operations are sufficiently rare, the massive amount of occasional work can be considered to blend in with the rest of the work as a constant factor. We say the work is "amortized" over a sufficiently large number of calls that it disappears asymptotically.

The analogy for amortized analysis:

You drive a car. Occasionally, you need to spend 10 minutes going to the gas station and then spend 1 minute refilling the tank with gas. If you did this every time you went anywhere with your car (spend 10 minutes driving to the gas station, spend a few seconds filling up a fraction of a gallon), it would be very inefficient. But if you fill up the tank once every few days, the 11 minutes spent driving to the gas station is "amortized" over a sufficiently large number of trips, that you can ignore it and pretend all your trips were maybe 5% longer.

Comparison between average-case and amortized worst-case:

  • Average-case: We make some assumptions about our inputs; ie if our inputs have different probabilities, then our outputs/runtimes will have different probabilities (which we take the average of). Usually we assume that our inputs are all equally likely (uniform probability), but if the real-world inputs don't fit our assumptions of "average input", the average output/runtime calculations may be meaningless. If you anticipate uniformly random inputs though, this is useful to think about!
  • Amortized worst-case: If you use an amortized worst-case data structure, the performance is guaranteed to be within the amortized worst-case... eventually (even if the inputs are chosen by an evil demon who knows everything and is trying to screw you over). Usually we use this to analyze algorithms which may be very 'choppy' in performance with unexpected large hiccups, but over time perform just as well as other algorithms. (However unless your data structure has upper limits for much outstanding work it is willing to procrastinate on, an evil attacker could perhaps force you to catch up on the maximum amount of procrastinated work all-at-once.

Though, if you're reasonably worried about an attacker, there are many other algorithmic attack vectors to worry about besides amortization and average-case.)

Both average-case and amortization are incredibly useful tools for thinking about and designing with scaling in mind.

(See Difference between average case and amortized analysis if interested on this subtopic.)


Multidimensional big-O

Most of the time, people don't realize that there's more than one variable at work. For example, in a string-search algorithm, your algorithm may take time O([length of text] + [length of query]) , ie it is linear in two variables like O(N+M) . Other more naive algorithms may be O([length of text]*[length of query]) or O(N*M) . Ignoring multiple variables is one of the most common oversights I see in algorithm analysis, and can handicap you when designing an algorithm.


The whole story

Keep in mind that big-O is not the whole story. You can drastically speed up some algorithms by using caching, making them cache-oblivious, avoiding bottlenecks by working with RAM instead of disk, using parallelization, or doing work ahead of time -- these techniques are often independent of the order-of-growth "big-O" notation, though you will often see the number of colors in the big-O notation of parallel algorithms.

Also keep in mind that due to hidden constraints of your program, you might not really care about asymptotic behavior. You may be working with a bounded number of values, for example:

  • If you're sorting something like 5 elements, you don't want to use the speedy O(N log(N)) quicksort; you want to use insertion sort, which happens to perform well on small inputs. These situations often comes up in divide-and-conquer algorithms, where you split up the problem into smaller and smaller subproblems, such as recursive sorting, fast Fourier transforms, or matrix multiplication.
  • If some values are effectively bounded due to some hidden fact (eg the average human name is softly bounded at perhaps 40 letters, and human age is softly bounded at around 150). You can also impose bounds on your input to effectively make terms constant.

In practice, even among algorithms which have the same or similar asymptotic performance, their relative merit may actually be driven by other things, such as: other performance factors (quicksort and mergesort are both O(N log(N)) , but quicksort takes advantage of CPU caches); non-performance considerations, like ease of implementation; whether a library is available, and how reputable and maintained the library is.

Programs will also run slower on a 500MHz computer vs 2GHz computer. We don't really consider this as part of the resource bounds, because we think of the scaling in terms of machine resources (eg per clock cycle), not per real second. However, there are similar things which can 'secretly' affect performance, such as whether you are running under emulation, or whether the compiler optimized code or not. These might make some basic operations take longer (even relative to each other), or even speed up or slow down some operations asymptotically (even relative to each other). The effect may be small or large between different implementation and/or environment. Do you switch languages or machines to eke out that little extra work? That depends on a hundred other reasons (necessity, skills, coworkers, programmer productivity, the monetary value of your time, familiarity, workarounds, why not assembly or GPU, etc...), which may be more important than performance.

The above issues, like programming language, are almost never considered as part of the constant factor (nor should they be); yet one should be aware of them, because sometimes (though rarely) they may affect things. For example in cpython, the native priority queue implementation is asymptotically non-optimal ( O(log(N)) rather than O(1) for your choice of insertion or find-min); do you use another implementation? Probably not, since the C implementation is probably faster, and there are probably other similar issues elsewhere. There are tradeoffs; sometimes they matter and sometimes they don't.


( edit : The "plain English" explanation ends here.)

Math addenda

For completeness, the precise definition of big-O notation is as follows: f(x) ∈ O(g(x)) means that "f is asymptotically upper-bounded by const*g": ignoring everything below some finite value of x, there exists a constant such that |f(x)| ≤ const * |g(x)| . (The other symbols are as follows: just like O means ≤, Ω means ≥. There are lowercase variants: o means <, and ω means >.) f(x) ∈ Ɵ(g(x)) means both f(x) ∈ O(g(x)) and f(x) ∈ Ω(g(x)) (upper- and lower-bounded by g): there exists some constants such that f will always lie in the "band" between const1*g(x) and const2*g(x) . It is the strongest asymptotic statement you can make and roughly equivalent to == . (Sorry, I elected to delay the mention of the absolute-value symbols until now, for clarity's sake; especially because I have never seen negative values come up in a computer science context.)

People will often use = O(...) , which is perhaps the more correct 'comp-sci' notation, and entirely legitimate to use... but one should realize = is not being used as equality; it is a compound notation that must be read as an idiom. I was taught to use the more rigorous ∈ O(...) . means "is an element of". O(N²) is actually an equivalence class , that is, it is a set of things which we consider to be the same. In this particular case, O(N²) contains elements like { 2 N² , 3 N² , 1/2 N² , 2 N² + log(N) , - N² + N^1.9 , ...} and is infinitely large, but it's still a set. The = notation might be the more common one, and is even used in papers by world-renowned computer scientists. Additionally, it is often the case that in a casual setting, people will say O(...) when they mean Ɵ(...) ; this is technically true since the set of things Ɵ(exactlyThis) is a subset of O(noGreaterThanThis) ... and it's easier to type. 😉

EDIT: Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is both an upper and lower bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

In one sentence: As the size of your job goes up, how much longer does it take to complete it?

Obviously that’s only using “size” as the input and “time taken” as the output — the same idea applies if you want to talk about memory usage etc.

Here’s an example where we have N T-shirts which we want to dry. We’ll assume it’s incredibly quick to get them in the drying position (ie the human interaction is negligible). That’s not the case in real life, of course…

  • Using a washing line outside: assuming you have an infinitely large back yard, washing dries in O(1) time. However much you have of it, it’ll get the same sun and fresh air, so the size doesn’t affect the drying time.

  • Using a tumble dryer: you put 10 shirts in each load, and then they’re done an hour later. (Ignore the actual numbers here — they’re irrelevant.) So drying 50 shirts takes about 5 times as long as drying 10 shirts.

  • Putting everything in an airing cupboard: If we put everything in one big pile and just let general warmth do it, it will take a long time for the middle shirts to get dry. I wouldn’t like to guess at the detail, but I suspect this is at least O(N^2) — as you increase the wash load, the drying time increases faster.

One important aspect of “big O” notation is that it doesn’t say which algorithm will be faster for a given size. Take a hashtable (string key, integer value) vs an array of pairs (string, integer). Is it faster to find a key in the hashtable or an element in the array, based on a string? (ie for the array, “find the first element where the string part matches the given key.”) Hashtables are generally amortised (~= “on average”) O(1) — once they’re set up, it should take about the same time to find an entry in a 100 entry table as in a 1,000,000 entry table. Finding an element in an array (based on content rather than index) is linear, ie O(N) — on average, you’re going to have to look at half the entries.

Does this make a hashtable faster than an array for lookups? Not necessarily. If you’ve got a very small collection of entries, an array may well be faster — you may be able to check all the strings in the time that it takes to just calculate the hashcode of the one you’re looking at. As the data set grows larger, however, the hashtable will eventually beat the array.

Big O describes an upper limit on the growth behaviour of a function, for example the runtime of a program, when inputs become large.

Exemplos:

  • O(n): If I double the input size the runtime doubles

  • O(n 2 ): If the input size doubles the runtime quadruples

  • O(log n): If the input size doubles the runtime increases by one

  • O(2 n ): If the input size increases by one, the runtime doubles

The input size is usually the space in bits needed to represent the input.

Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.

Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.

More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.

In many cases the “O” of an algorithm will fall into one of the following cases:

  • O(1) – Time to complete is the same regardless of the size of input set. An example is accessing an array element by index.
  • O(Log N) – Time to complete increases roughly in line with the log2(n). For example 1024 items takes roughly twice as long as 32 items, because Log2(1024) = 10 and Log2(32) = 5. An example is finding an item in a binary search tree (BST).
  • O(N) – Time to complete that scales linearly with the size of the input set. In other words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example is counting the number of items in a linked list.
  • O(N Log N) – Time to complete increases by the number of items times the result of Log2(N). An example of this is heap sort and quick sort .
  • O(N^2) – Time to complete is roughly equal to the square of the number of items. An example of this is bubble sort .
  • O(N!) – Time to complete is the factorial of the input set. An example of this is the traveling salesman problem brute-force solution .

Big O ignores factors that do not contribute in a meaningful way to the growth curve of a function as the input size increases towards infinity. This means that constants that are added to or multiplied by the function are simply ignored.

Big O is just a way to “Express” yourself in a common way, “How much time / space does it take to run my code?”.

You may often see O(n), O(n 2 ), O(nlogn) and so forth, all these are just ways to show; How does an algorithm change?

O(n) means Big O is n, and now you might think, “What is n!?” Well “n” is the amount of elements. Imaging you want to search for an Item in an Array. You would have to look on Each element and as “Are you the correct element/item?” in the worst case, the item is at the last index, which means that it took as much time as there are items in the list, so to be generic, we say “oh hey, n is a fair given amount of values!”.

So then you might understand what “n 2 ” means, but to be even more specific, play with the thought you have a simple, the simpliest of the sorting algorithms; bubblesort. This algorithm needs to look through the whole list, for each item.

Minha lista

  1. 1
  2. 6
  3. 3

The flow here would be:

  • Compare 1 and 6, which is biggest? Ok 6 is in the right position, moving forward!
  • Compare 6 and 3, oh, 3 is less! Let’s move that, Ok the list changed, we need to start from the begining now!

This is O n 2 because, you need to look at all items in the list there are “n” items. For each item, you look at all items once more, for comparing, this is also “n”, so for every item, you look “n” times meaning n*n = n 2

I hope this is as simple as you want it.

But remember, Big O is just a way to experss yourself in the manner of time and space.

Big O describes the fundamental scaling nature of an algorithm.

There is a lot of information that Big O does not tell you about a given algorithm. It cuts to the bone and gives only information about the scaling nature of an algorithm, specifically how the resource use (think time or memory) of an algorithm scales in response to the “input size”.

Consider the difference between a steam engine and a rocket. They are not merely different varieties of the same thing (as, say, a Prius engine vs. a Lamborghini engine) but they are dramatically different kinds of propulsion systems, at their core. A steam engine may be faster than a toy rocket, but no steam piston engine will be able to achieve the speeds of an orbital launch vehicle. This is because these systems have different scaling characteristics with regards to the relation of fuel required (“resource usage”) to reach a given speed (“input size”).

Why is this so important? Because software deals with problems that may differ in size by factors up to a trillion. Consider that for a moment. The ratio between the speed necessary to travel to the Moon and human walking speed is less than 10,000:1, and that is absolutely tiny compared to the range in input sizes software may face. And because software may face an astronomical range in input sizes there is the potential for the Big O complexity of an algorithm, it’s fundamental scaling nature, to trump any implementation details.

Consider the canonical sorting example. Bubble-sort is O(n 2 ) while merge-sort is O(n log n). Let’s say you have two sorting applications, application A which uses bubble-sort and application B which uses merge-sort, and let’s say that for input sizes of around 30 elements application A is 1,000x faster than application B at sorting. If you never have to sort much more than 30 elements then it’s obvious that you should prefer application A, as it is much faster at these input sizes. However, if you find that you may have to sort ten million items then what you’d expect is that application B actually ends up being thousands of times faster than application A in this case, entirely due to the way each algorithm scales.

Here is the plain English bestiary I tend to use when explaining the common varieties of Big-O

In all cases, prefer algorithms higher up on the list to those lower on the list. However, the cost of moving to a more expensive complexity class varies significantly.

O(1):

No growth. Regardless of how big as the problem is, you can solve it in the same amount of time. This is somewhat analogous to broadcasting where it takes the same amount of energy to broadcast over a given distance, regardless of the number of people that lie within the broadcast range.

O(log n ):

This complexity is the same as O(1) except that it’s just a little bit worse. For all practical purposes, you can consider this as a very large constant scaling. The difference in work between processing 1 thousand and 1 billion items is only a factor six.

O( n ):

The cost of solving the problem is proportional to the size of the problem. If your problem doubles in size, then the cost of the solution doubles. Since most problems have to be scanned into the computer in some way, as data entry, disk reads, or network traffic, this is generally an affordable scaling factor.

O( n log n ):

This complexity is very similar to O( n ) . For all practical purposes, the two are equivalent. This level of complexity would generally still be considered scalable. By tweaking assumptions some O( n log n ) algorithms can be transformed into O( n ) algorithms. For example, bounding the size of keys reduces sorting from O( n log n ) to O( n ) .

O( n 2 ):

Grows as a square, where n is the length of the side of a square. This is the same growth rate as the “network effect”, where everyone in a network might know everyone else in the network. Growth is expensive. Most scalable solutions cannot use algorithms with this level of complexity without doing significant gymnastics. This generally applies to all other polynomial complexities – O( n k ) – as well.

O(2 n ):

Does not scale. You have no hope of solving any non-trivially sized problem. Useful for knowing what to avoid, and for experts to find approximate algorithms which are in O( n k ) .

Big O is a measure of how much time/space an algorithm uses relative to the size of its input.

If an algorithm is O(n) then the time/space will increase at the same rate as its input.

If an algorithm is O(n 2 ) then the time/space increase at the rate of its input squared.

e assim por diante.

It is very difficult to measure the speed of software programs, and when we try, the answers can be very complex and filled with exceptions and special cases. This is a big problem, because all those exceptions and special cases are distracting and unhelpful when we want to compare two different programs with one another to find out which is “fastest”.

As a result of all this unhelpful complexity, people try to describe the speed of software programs using the smallest and least complex (mathematical) expressions possible. These expressions are very very crude approximations: Although, with a bit of luck, they will capture the “essence” of whether a piece of software is fast or slow.

Because they are approximations, we use the letter “O” (Big Oh) in the expression, as a convention to signal to the reader that we are making a gross oversimplification. (And to make sure that nobody mistakenly thinks that the expression is in any way accurate).

If you read the “Oh” as meaning “on the order of” or “approximately” you will not go too far wrong. (I think the choice of the Big-Oh might have been an attempt at humour).

The only thing that these “Big-Oh” expressions try to do is to describe how much the software slows down as we increase the amount of data that the software has to process. If we double the amount of data that needs to be processed, does the software need twice as long to finish it’s work? Ten times as long? In practice, there are a very limited number of big-Oh expressions that you will encounter and need to worry about:

The good:

  • O(1) Constant : The program takes the same time to run no matter how big the input is.
  • O(log n) Logarithmic : The program run-time increases only slowly, even with big increases in the size of the input.

The bad:

  • O(n) Linear : The program run-time increases proportionally to the size of the input.
  • O(n^k) Polynomial : – Processing time grows faster and faster – as a polynomial function – as the size of the input increases.

… and the ugly:

  • O(k^n) Exponential The program run-time increases very quickly with even moderate increases in the size of the problem – it is only practical to process small data sets with exponential algorithms.
  • O(n!) Factorial The program run-time will be longer than you can afford to wait for anything but the very smallest and most trivial-seeming datasets.

What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

A Plain English Explanation of the Need for Big-O Notation:

When we program, we are trying to solve a problem. What we code is called an algorithm. Big O notation allows us to compare the worse case performance of our algorithms in a standardized way. Hardware specs vary over time and improvements in hardware can reduce the time it takes an algorithms to run. But replacing the hardware does not mean our algorithm is any better or improved over time, as our algorithm is still the same. So in order to allow us to compare different algorithms, to determine if one is better or not, we use Big O notation.

A Plain English Explanation of What Big O Notation is:

Not all algorithms run in the same amount of time, and can vary based on the number of items in the input, which we’ll call n . Based on this, we consider the worse case analysis, or an upper-bound of the run-time as n get larger and larger. We must be aware of what n is, because many of the Big O notations reference it.

A simple straightforward answer can be:

Big O represents the worst possible time/space for that algorithm. The algorithm will never take more space/time above that limit. Big O represents time/space complexity in the extreme case.

Ok, my 2cents.

Big-O, is rate of increase of resource consumed by program, wrt problem-instance-size

Resource : Could be total-CPU time, could be maximum RAM space. By default refers to CPU time.

Say the problem is “Find the sum”,

 int Sum(int*arr,int size){ int sum=0; while(size-->0) sum+=arr[size]; return sum; } 

problem-instance= {5,10,15} ==> problem-instance-size = 3, iterations-in-loop= 3

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5 iterations-in-loop = 5

For input of size “n” the program is growing at speed of “n” iterations in array. Hence Big-O is N expressed as O(n)

Say the problem is “Find the Combination”,

  void Combination(int*arr,int size) { int outer=size,inner=size; while(outer -->0) { inner=size; while(inner -->0) cout< 

problem-instance= {5,10,15} ==> problem-instance-size = 3, total-iterations = 3*3 = 9

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations= 5*5 =25

For input of size "n" the program is growing at speed of "n*n" iterations in array. Hence Big-O is N 2 expressed as O(n 2 )

Big O notation is a way of describing the upper bound of an algorithm in terms of space or running time. The n is the number of elements in the the problem (ie size of an array, number of nodes in a tree, etc.) We are interested in describing the running time as n gets big.

When we say some algorithm is O(f(n)) we are saying that the running time (or space required) by that algorithm is always lower than some constant times f(n).

To say that binary search has a running time of O(logn) is to say that there exists some constant c which you can multiply log(n) by that will always be larger than the running time of binary search. In this case you will always have some constant factor of log(n) comparisons.

In other words where g(n) is the running time of your algorithm, we say that g(n) = O(f(n)) when g(n) <= c*f(n) when n > k, where c and k are some constants.

What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

Such a beautifully simple and short question seems at least to deserve an equally short answer, like a student might receive during tutoring.

Big O notation simply tells how much time* an algorithm can run within, in terms of only the amount of input data **.

( *in a wonderful, unit-free sense of time!)
(**which is what matters, because people will always want more , whether they live today or tomorrow)

Well, what’s so wonderful about Big O notation if that’s what it does?

  • Practically speaking, Big O analysis is so useful and important because Big O puts the focus squarely on the algorithm’s own complexity and completely ignores anything that is merely a proportionality constant—like a JavaScript engine, the speed of a CPU, your Internet connection, and all those things which become quickly become as laughably outdated as a Model T . Big O focuses on performance only in the way that matters equally as much to people living in the present or in the future.

  • Big O notation also shines a spotlight directly on the most important principle of computer programming/engineering, the fact which inspires all good programmers to keep thinking and dreaming: the only way to achieve results beyond the slow forward march of technology is to invent a better algorithm .

Algorithm example (Java):

 // given a list of integers L, and an integer K public boolean simple_search(List L, Integer K) { // for each integer i in list L for (Integer i : L) { // if i is equal to K if (i == K) { return true; } } return false; } 

Algorithm description:

  • This algorithm search a list, item by item, looking for a key,

  • Iterating on each item in the list, if it’s the key then return True,

  • If the loop has finished without finding the key, return False.

Big-O notation represent the upper-bound on the Complexity (Time, Space, ..)

To find The Big-O on Time Complexity:

  • Calculate how much time (regarding input size) the worst case takes:

  • Worst-Case: the key doesn’t exist in the list.

  • Time(Worst-Case) = 4n+1

  • Time: O(4n+1) = O(n) | in Big-O, constants are neglected

  • O(n) ~ Linear

There’s also Big-Omega, which represent complexity of the Best-Case:

  • Best-Case: the key is the first item.

  • Time(Best-Case) = 4

  • Time: Ω(4) = O(1) ~ Instant\Constant

Big O

f (x) = O( g (x)) when x goes to a (for example, a = +∞) means that there is a function k such that:

  1. f (x) = k (x) g (x)

  2. k is bounded in some neighborhood of a (if a = +∞, this means that there are numbers N and M such that for every x > N, | k (x)| < M).

In other words, in plain English: f (x) = O( g (x)), x → a, means that in a neighborhood of a, f decomposes into the product of g and some bounded function.

Small o

By the way, here is for comparison the definition of small o.

f (x) = o( g (x)) when x goes to a means that there is a function k such that:

  1. f (x) = k (x) g (x)

  2. k (x) goes to 0 when x goes to a.

Exemplos

  • sin x = O(x) when x → 0.

  • sin x = O(1) when x → +∞,

  • x 2 + x = O(x) when x → 0,

  • x 2 + x = O(x 2 ) when x → +∞,

  • ln(x) = o(x) = O(x) when x → +∞.

Attention! The notation with the equal sign “=” uses a “fake equality”: it is true that o(g(x)) = O(g(x)), but false that O(g(x)) = o(g(x)). Similarly, it is ok to write “ln(x) = o(x) when x → +∞”, but the formula “o(x) = ln(x)” would make no sense.

Mais exemplos

  • O(1) = O(n) = O(n 2 ) when n → +∞ (but not the other way around, the equality is “fake”),

  • O(n) + O(n 2 ) = O(n 2 ) when n → +∞

  • O(O(n 2 )) = O(n 2 ) when n → +∞

  • O(n 2 )O(n 3 ) = O(n 5 ) when n → +∞


Here is the Wikipedia article: https://en.wikipedia.org/wiki/Big_O_notation

Big O notation is a way of describing how quickly an algorithm will run given an arbitrary number of input parameters, which we’ll call “n”. It is useful in computer science because different machines operate at different speeds, and simply saying that an algorithm takes 5 seconds doesn’t tell you much because while you may be running a system with a 4.5 Ghz octo-core processor, I may be running a 15 year old, 800 Mhz system, which could take longer regardless of the algorithm. So instead of specifying how fast an algorithm runs in terms of time, we say how fast it runs in terms of number of input parameters, or “n”. By describing algorithms in this way, we are able to compare the speeds of algorithms without having to take into account the speed of the computer itself.

Not sure I’m further contributing to the subject but still thought I’d share: I once found this blog post to have some quite helpful (though very basic) explanations & examples on Big O:

Via examples, this helped get the bare basics into my tortoiseshell-like skull, so I think it’s a pretty descent 10-minute read to get you headed in the right direction.

You want to know all there is to know of big O? So do I.

So to talk of big O, I will use words that have just one beat in them. One sound per word. Small words are quick. You know these words, and so do I. We will use words with one sound. They are small. I am sure you will know all of the words we will use!

Now, let’s you and me talk of work. Most of the time, I do not like work. Do you like work? It may be the case that you do, but I am sure I do not.

I do not like to go to work. I do not like to spend time at work. If I had my way, I would like just to play, and do fun things. Do you feel the same as I do?

Now at times, I do have to go to work. It is sad, but true. So, when I am at work, I have a rule: I try to do less work. As near to no work as I can. Then I go play!

So here is the big news: the big O can help me not to do work! I can play more of the time, if I know big O. Less work, more play! That is what big O helps me do.

Now I have some work. I have this list: one, two, three, four, five, six. I must add all things in this list.

Wow, I hate work. But oh well, I have to do this. So here I go.

One plus two is three… plus three is six… and four is… I don’t know. I got lost. It is too hard for me to do in my head. I don’t much care for this kind of work.

So let’s not do the work. Let’s you and me just think how hard it is. How much work would I have to do, to add six numbers?

Well, let’s see. I must add one and two, and then add that to three, and then add that to four… All in all, I count six adds. I have to do six adds to solve this.

Here comes big O, to tell us just how hard this math is.

Big O says: we must do six adds to solve this. One add, for each thing from one to six. Six small bits of work… each bit of work is one add.

Well, I will not do the work to add them now. But I know how hard it would be. It would be six adds.

Oh no, now I have more work. Sheesh. Who makes this kind of stuff?!

Now they ask me to add from one to ten! Why would I do that? I did not want to add one to six. To add from one to ten… well… that would be even more hard!

How much more hard would it be? How much more work would I have to do? Do I need more or less steps?

Well, I guess I would have to do ten adds… one for each thing from one to ten. Ten is more than six. I would have to work that much more to add from one to ten, than one to six!

I do not want to add right now. I just want to think on how hard it might be to add that much. And, I hope, to play as soon as I can.

To add from one to six, that is some work. But do you see, to add from one to ten, that is more work?

Big O is your friend and mine. Big O helps us think on how much work we have to do, so we can plan. And, if we are friends with big O, he can help us choose work that is not so hard!

Now we must do new work. Oh, no. I don’t like this work thing at all.

The new work is: add all things from one to n.

Wait! What is n? Did I miss that? How can I add from one to n if you don’t tell me what n is?

Well, I don’t know what n is. I was not told. Were you? No? Oh well. So we can’t do the work. Whew.

But though we will not do the work now, we can guess how hard it would be, if we knew n. We would have to add up n things, right? Of course!

Now here comes big O, and he will tell us how hard this work is. He says: to add all things from one to N, one by one, is O(n). To add all these things, [I know I must add n times.][1] That is big O! He tells us how hard it is to do some type of work.

To me, I think of big O like a big, slow, boss man. He thinks on work, but he does not do it. He might say, “That work is quick.” Or, he might say, “That work is so slow and hard!” But he does not do the work. He just looks at the work, and then he tells us how much time it might take.

I care lots for big O. Why? I do not like to work! No one likes to work. That is why we all love big O! He tells us how fast we can work. He helps us think of how hard work is.

Uh oh, more work. Now, let’s not do the work. But, let’s make a plan to do it, step by step.

They gave us a deck of ten cards. They are all mixed up: seven, four, two, six… not straight at all. And now… our job is to sort them.

Ergh. That sounds like a lot of work!

How can we sort this deck? I have a plan.

I will look at each pair of cards, pair by pair, through the deck, from first to last. If the first card in one pair is big and the next card in that pair is small, I swap them. Else, I go to the next pair, and so on and so on… and soon, the deck is done.

When the deck is done, I ask: did I swap cards in that pass? If so, I must do it all once more, from the top.

At some point, at some time, there will be no swaps, and our sort of the deck would be done. So much work!

Well, how much work would that be, to sort the cards with those rules?

I have ten cards. And, most of the time — that is, if I don’t have lots of luck — I must go through the whole deck up to ten times, with up to ten card swaps each time through the deck.

Big O, help me!

Big O comes in and says: for a deck of n cards, to sort it this way will be done in O(N squared) time.

Why does he say n squared?

Well, you know n squared is n times n. Now, I get it: n cards checked, up to what might be n times through the deck. That is two loops, each with n steps. That is n squared much work to be done. A lot of work, for sure!

Now when big O says it will take O(n squared) work, he does not mean n squared adds, on the nose. It might be some small bit less, for some case. But in the worst case, it will be near n squared steps of work to sort the deck.

Now here is where big O is our friend.

Big O points out this: as n gets big, when we sort cards, the job gets MUCH MUCH MORE HARD than the old just-add-these-things job. How do we know this?

Well, if n gets real big, we do not care what we might add to n or n squared.

For big n, n squared is more large than n.

Big O tells us that to sort things is more hard than to add things. O(n squared) is more than O(n) for big n. That means: if n gets real big, to sort a mixed deck of n things MUST take more time, than to just add n mixed things.

Big O does not solve the work for us. Big O tells us how hard the work is.

I have a deck of cards. I did sort them. You helped. Obrigado.

Is there a more fast way to sort the cards? Can big O help us?

Yes, there is a more fast way! It takes some time to learn, but it works… and it works quite fast. You can try it too, but take your time with each step and do not lose your place.

In this new way to sort a deck, we do not check pairs of cards the way we did a while ago. Here are your new rules to sort this deck:

One: I choose one card in the part of the deck we work on now. You can choose one for me if you like. (The first time we do this, “the part of the deck we work on now” is the whole deck, of course.)

Two: I splay the deck on that card you chose. What is this splay; how do I splay? Well, I go from the start card down, one by one, and I look for a card that is more high than the splay card.

Three: I go from the end card up, and I look for a card that is more low than the splay card.

Once I have found these two cards, I swap them, and go on to look for more cards to swap. That is, I go back to step Two, and splay on the card you chose some more.

At some point, this loop (from Two to Three) will end. It ends when both halves of this search meet at the splay card. Then, we have just splayed the deck with the card you chose in step One. Now, all the cards near the start are more low than the splay card; and the cards near the end are more high than the splay card. Cool trick!

Four (and this is the fun part): I have two small decks now, one more low than the splay card, and one more high. Now I go to step one, on each small deck! That is to say, I start from step One on the first small deck, and when that work is done, I start from step One on the next small deck.

I break up the deck in parts, and sort each part, more small and more small, and at some time I have no more work to do. Now this may seem slow, with all the rules. But trust me, it is not slow at all. It is much less work than the first way to sort things!

What is this sort called? It is called Quick Sort! That sort was made by a man called CAR Hoare and he called it Quick Sort. Now, Quick Sort gets used all the time!

Quick Sort breaks up big decks in small ones. That is to say, it breaks up big tasks in small ones.

Hmmm There may be a rule in there, I think. To make big tasks small, break them up.

This sort is quite quick. How quick? Big O tells us: this sort needs O(n log n) work to be done, in the mean case.

Is it more or less fast than the first sort? Big O, please help!

The first sort was O(n squared). But Quick Sort is O(n log n). You know that n log n is less than n squared, for big n, right? Well, that is how we know that Quick Sort is fast!

If you have to sort a deck, what is the best way? Well, you can do what you want, but I would choose Quick Sort.

Why do I choose Quick Sort? I do not like to work, of course! I want work done as soon as I can get it done.

How do I know Quick Sort is less work? I know that O(n log n) is less than O(n squared). The O’s are more small, so Quick Sort is less work!

Now you know my friend, Big O. He helps us do less work. And if you know big O, you can do less work too!

You learned all that with me! You are so smart! Muito obrigado!

Now that work is done, let’s go play!


[1]: There is a way to cheat and add all the things from one to n, all at one time. Some kid named Gauss found this out when he was eight. I am not that smart though, so don’t ask me how he did it .

Assume we’re talking about an algorithm A , which should do something with a dataset of size n .

Then O( ) means, in simple English:

If you’re unlucky when executing A, it might take X(n) operations to complete.

As it happens, there are certain functions (think of them as implementations of X(n) ) that tend to occur quite often. These are well known and easily compared (Examples: 1 , Log N , N , N^2 , N! , etc..)

By comparing these when talking about A and other algorithms, it is easy to rank the algorithms according to the number of operations they may (worst-case) require to complete.

In general, our goal will be to find or structure an algorithm A in such a way that it will have a function X(n) that returns as low a number as possible.

I’ve more simpler way to understand the time complexity he most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

 statement; 

Is constant. The running time of the statement will not change in relation to N

 for ( i = 0; i < N; i++ ) statement; 

Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; } 

Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( ) where is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

Note: None of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.

  • See more at: Here

Say you order Harry Potter: Complete 8-Film Collection [Blu-ray] from Amazon and download the same film collection online at the same time. You want to test which method is faster. The delivery takes almost a day to arrive and the download completed about 30 minutes earlier. Ótimo! So it’s a tight race.

What if I order several Blu-ray movies like The Lord of the Rings, Twilight, The Dark Knight Trilogy, etc. and download all the movies online at the same time? This time, the delivery still take a day to complete, but the online download takes 3 days to finish. For online shopping, the number of purchased item (input) doesn’t affect the delivery time. The output is constant. We call this O(1) .

For online downloading, the download time is directly proportional to the movie file sizes (input). We call this O(n) .

From the experiments, we know that online shopping scales better than online downloading. It is very important to understand big O notation because it helps you to analyze the scalability and efficiency of algorithms.

Note: Big O notation represents the worst-case scenario of an algorithm. Let’s assume that O(1) and O(n) are the worst-case scenarios of the example above.

Reference : http://carlcheo.com/compsci

If you have a suitable notion of infinity in your head, then there is a very brief description:

Big O notation tells you the cost of solving an infinitely large problem.

And furthermore

Constant factors are negligible

If you upgrade to a computer that can run your algorithm twice as fast, big O notation won’t notice that. Constant factor improvements are too small to even be noticed in the scale that big O notation works with. Note that this is an intentional part of the design of big O notation.

Although anything “larger” than a constant factor can be detected, however.

When interested in doing computations whose size is “large” enough to be considered as approximately infinity, then big O notation is approximately the cost of solving your problem.


If the above doesn’t make sense, then you don’t have a compatible intuitive notion of infinity in your head, and you should probably disregard all of the above; the only way I know to make these ideas rigorous, or to explain them if they aren’t already intuitively useful, is to first teach you big O notation or something similar. (although, once you well understand big O notation in the future, it may be worthwhile to revisit these ideas)

Simplest way to look at it (in plain English)

We are trying to see how the number of input parameters, affects the running time of an algorithm. If the running time of your application is proportional to the number of input parameters, then it is said to be in Big O of n.

The above statement is a good start but not completely true.

A more accurate explanation (mathematical)

Suppose

n=number of input parameters

T(n)= The actual function that expresses the running time of the algorithm as a function of n

c= a constant

f(n)= An approximate function that expresses the running time of the algorithm as a function of n

Then as far as Big O is concerned, the approximation f(n) is considered good enough as long as the below condition is true.

 lim T(n) ≤ c×f(n) n→∞ 

The equation is read as As n approaches infinity, T of n, is less than or equal to c times f of n.

In big O notation this is written as

 T(n)∈O(n) 

This is read as T of n is in big O of n.

Back to English

Based on the mathematical definition above, if you say your algorithm is a Big O of n, it means it is a function of n (number of input parameters) or faster . If your algorithm is Big O of n, then it is also automatically the Big O of n square.

Big O of n means my algorithm runs at least as fast as this. You cannot look at Big O notation of your algorithm and say its slow. You can only say its fast.

Check this out for a video tutorial on Big O from UC Berkley. It’s is actually a simple concept. If you hear professor Shewchuck (aka God level teacher) explaining it, you will say “Oh that’s all it is!”.

What is a plain English explanation of “Big O” notation?

Very Quick Note:

The O in “Big O” refers to as “Order”(or precisely “order of”)
so you could get its idea literally that it’s used to order something to compare them.

  • “Big O” does two things:

    1. Estimates how many steps of the method your computer applies to accomplish a task.
    2. Facilitate the process to compare with others in order to determine whether it’s good or not?
    3. “Big O’ achieves the above two with standardized Notations .
  • There are seven most used notations

    1. O(1), means your computer gets a task done with 1 step, it’s excellent, Ordered No.1
    2. O(logN), means your computer complete a task with logN steps, its good, Ordered No.2
    3. O(N), finish a task with N steps, its fair, Order No.3
    4. O(NlogN), ends a task with O(NlogN) steps, it’s not good, Order No.4
    5. O(N^2), get a task done with N^2 steps, it’s bad, Order No.5
    6. O(2^N), get a task done with 2^N steps, it’s horrible, Order No.6
    7. O(N!), get a task done with N! steps, it’s terrible, Order No.7

insira a descrição da imagem aqui

Suppose you get notation O(N^2) , not only you are clear the method takes N*N steps to accomplish a task, also you see that it’s not good as O(NlogN) from its ranking.

Please note the order at line end, just for your better understanding.There’s more than 7 notations if all possibilities considered.

In CS, the set of steps to accomplish a task is called algorithms.
In Terminology, Big O notation is used to describe the performance or complexity of an algorithm.

In addition, Big O establishes the worst-case or measure the Upper-Bound steps.
You could refer to Big-Ω (Big-Omega) for best case.

Big-Ω (Big-Omega) notation (article) | Khan Academy

  • Resumo
    “Big O” describes the algorithm’s performance and evaluates it.

    or address it formally, “Big O” classifies the algorithms and standardize the comparison process.

This is a very simplified explanation, but I hope it covers most important details.

Let’s say your algorithm dealing with the problem depends on some ‘factors’, for example let’s make it N and X.

Depending on N and X, your algorithm will require some operations, for example in the WORST case it’s 3(N^2) + log(X) operations.

Since Big-O doesn’t care too much about constant factor (aka 3), the Big-O of your algorithm is O(N^2 + log(X)) . It basically translates ‘the amount of operations your algorithm needs for the worst case scales with this’.

Definition :- Big O notation is a notation which says how a algorithm performance will perform if the data input increases.

When we talk about algorithms there are 3 important pillars Input , Output and Processing of algorithm. Big O is symbolic notation which says if the data input is increased in what rate will the performance vary of the algorithm processing.

I would encourage you to see this youtube video which explains Big O Notation in depth with code examples.

Algorithm basic pillars

So for example assume that a algorithm takes 5 records and the time required for processing the same is 27 seconds. Now if we increase the records to 10 the algorithm takes 105 seconds.

In simple words the time taken is square of the number of records. We can denote this by O(n ^ 2) . This symbolic representation is termed as Big O notation.

Now please note the units can be anything in inputs it can be bytes , bits number of records , the performance can be measured in any unit like second , minutes , days and so on. So its not the exact unit but rather the relationship.

Big O symbols

For example look at the below function “Function1” which takes a collection and does processing on the first record. Now for this function the performance will be same irrespective you put 1000 , 10000 or 100000 records. So we can denote it by O(1) .

 void Function1(List data) { string str = data[0]; } 

Now see the below function “Function2()”. In this case the processing time will increase with number of records. We can denote this algorithm performance using O(n) .

 void Function2(List data) { foreach(string str in data) { if (str == "shiv") { return; } } } 

When we see a Big O notation for any algorithm we can classify them in to three categories of performance :-

  1. Log and constant category :- Any developer would love to see their algorithm performance in this category.
  2. Linear :- Developer will not want to see algorithms in this category , until its the last option or the only option left.
  3. Exponential :- This is where we do not want to see our algorithms and a rework is needed.

So by looking at Big O notation we categorize good and bad zones for algorithms.

Bog O classification

I would recommend you to watch this 10 minutes video which discusses Big O with sample code

https://www.youtube.com/watch?v=k6kxtzICG_g

If I want to explain this to 6 years old child I will start to draw some functions f(x) = x and f(x) = x^2 for example and ask a child which function will be upper function on the top of the page. Then we will proceed with drawing and see that x^2 wins. “Who wins” actually is the function which grows faster when x tends to infinity. So “function x is in Big O of x^2” means that x grows slower than x^2 when x tends to infinity. The same can be done when x tends to 0. If we draw these two function for x from 0 to 1 x will be upper function, so “function x^2 is in Big O of x for x tends to 0”. When child will get older I add that really Big O can be a function which grows not faster but the same way as given function. Moreover constant is discarded. So 2x is in Big O of x.