# Big O Notation

### Definição

Quando se estuda algoritmos, é comum ouvir dois termos, _time complexity_ e _space complexity_. Eles se referem respectivamente à quantidade de tempo que um algoritmo leva para ser concluído e à quantidade de memória utilizada para concluir um algoritmo dado input de tamanho N.&#x20;

Big O Notation é uma notação para analisarmos tanto a _time complexity_ quanto a _space complexity_ de um algoritmo, dentre muitas outras, geralmente considerando o pior cenário. É importante conhecer Big O para entendermos a performance de um algoritmo, quanto para melhorá-lo.&#x20;



<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2Fthzmuvq3YpKw3qqGQ1WS%2FScreenshot%202024-12-12%20at%2013.35.14.png?alt=media&#x26;token=1934bfc8-d473-45f7-a140-cf1105e66dd6" alt=""><figcaption></figcaption></figure>

### Complexidades Mais Comuns

Pense no valor dentro de parênteses como a quantidade de vezes em que seu algoritmo será executado a depender do tamanho do seu input.&#x20;



Nesse caso, O (1) é tempo constante, sempre vai levar a mesma quantidade de tempo independente do input. Um exemplo de um algoritmo de tempo constante é uma simples operação matemática:

```python
def sum(n): 
    return n * 2
```



Ou seja, O (log N) trata-se de um algoritmo que dado um input será executado literalmente log(N) vezes, o que é muito devagar, log(1000000) é cerca de apenas 20 execuções! Um algoritmo bem famoso que é O (log N) é a [busca binária](https://fernando-2.gitbook.io/dsa-docs/algorithms/binary-search).&#x20;



O (N) é um algoritmo de tempo linear, ou seja, cresce linearmente com o tamanho do input, um clássico for loop percorrendo um array de tamanho N por exemplo:&#x20;

```python
for i in n:
    print(i)
```



O (K log N) é um algoritmo que vai ser executado K \* log (N), por exemplo, fazer K buscas binárias.



O (N^2) é uma complexidade de tempo quadrática, ou seja, para o input N, será executado Nˆ2 vezes.&#x20;

```python
for i in range(1, N + 1):
  for j in range(1, N + 1):
    print(i, j)
```



O (2^N) é um algoritmo, literalmente, exponencial, cresce insanamente rápido.&#x20;

```python
def Fib(n):
  if n == 0 or n == 1:
    return 1
  return Fib(n - 1) + Fib(n - 2)
```



O (N!) cresce ainda insanamente mais rápido do que um complexidade de tempo exponencial.
