Analisar
Big O Reference • JavaScript • Python • Java

Exemplos de Complexidade Big O

Exemplos simples e autocontidos de complexidades de tempo comuns, em Python, JavaScript e Java. Todos os exemplos consideram o pior cenário.

Visão geral

Intuição e casos de uso típicos para cada complexidade de tempo assintótica (pior caso).

ComplexidadeNomeIntuiçãoCaso de uso típico
O(1)ConstanteTempo não cresce com o tamanho da entradaAcesso direto a índice, hash lookup
O(log n)LogarítmicaDobra o tamanho, adiciona apenas um passoBusca binária
O(n)LinearTempo cresce proporcionalmente ao tamanho da entradaVarredura simples (loops)
O(n log n)LinearítmicaQuase linear, mas com custo de divisão/combinaçãoSorts eficientes (Merge, Quick)
O(n²)QuadráticaLoops aninhados sobre a mesma coleçãoComparações par-a-par
O(2ⁿ)ExponencialExplora todas as combinações possíveis de n elementosProblemas de decisão com backtracking
O(n!)FatorialGera todas as permutações de n elementosGeração de todas as ordens possíveis

1. Constante

O(1) – Tempo constante

Ideia: o tempo de execução não depende do tamanho da entrada. Exemplo clássico: acessar o primeiro elemento de um array.

JavaScript
// O(1) - Acesso constante ao primeiro elemento
function getFirstElement(arr) {
  // Sempre 1 acesso, independentemente do tamanho de arr
  return arr[0];
}

const nums = [10, 20, 30, 40];
console.log(getFirstElement(nums));
Python
# O(1) - Acesso constante ao primeiro elemento

def get_first_element(arr):
    # Retorna sempre o primeiro elemento do array (tempo constante)
    return arr[0]


nums = [10, 20, 30, 40]
print(get_first_element(nums))
Java
// O(1) - Acesso constante ao primeiro elemento
public class BigOConstant {
    public static int getFirstElement(int[] arr) {
        // Sempre 1 acesso
        return arr[0];
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 40};
        System.out.println(getFirstElement(nums));
    }
}

2. Logarítmica

O(log n) – Busca binária

Ideia: a cada passo, o espaço de busca é reduzido pela metade. Pior caso: o elemento não está presente — percorremos aproximadamente log₂(n) passos.

JavaScript
// O(log n) - Busca binária em array ORDENADO

function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sortedArr[mid] === target) {
      return mid;
    }

    if (sortedArr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // Pior caso: não encontrado
  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9], 7));
Python
# O(log n) - Busca binária em array ORDENADO

def binary_search(sorted_arr, target):
    left = 0
    right = len(sorted_arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_arr[mid] == target:
            return mid
        if sorted_arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # Pior caso: não encontrado
    return -1


print(binary_search([1, 3, 5, 7, 9], 7))
Java
// O(log n) - Busca binária em array ORDENADO

public class BigOLogN {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // Pior caso: não encontrado
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(arr, 7));
    }
}

3. Linear

O(n) – Busca linear

Ideia: o tempo de execução cresce proporcionalmente ao tamanho da entrada. Pior caso: o elemento não está presente (ou está na última posição).

JavaScript
// O(n) - Busca linear

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  // Pior caso: não encontrado
  return -1;
}

console.log(linearSearch([1, 2, 3, 4, 5], 4));
Python
# O(n) - Busca linear

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    # Pior caso: percorre o array inteiro
    return -1


print(linear_search([1, 2, 3, 4, 5], 4))
Java
// O(n) - Busca linear

public class BigON {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        // Pior caso: não encontrado
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(linearSearch(arr, 4));
    }
}

4. Linearítmica

O(n log n) – Merge Sort

Ideia: o array é dividido recursivamente ao meio (parte log n) e depois mesclado (parte n). Pior caso: Merge Sort sempre executa em O(n log n).

JavaScript
// O(n log n) - Merge Sort

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

console.log(mergeSort([5, 3, 8, 4, 2, 7, 1, 6]));
Python
# O(n log n) - Merge Sort

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


print(merge_sort([5, 3, 8, 4, 2, 7, 1, 6]))
Java
// O(n log n) - Merge Sort

import java.util.Arrays;

public class BigONLogN {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        int mid = arr.length / 2;

        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    private static void merge(int[] dest, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                dest[k++] = left[i++];
            } else {
                dest[k++] = right[j++];
            }
        }

        while (i < left.length) {
            dest[k++] = left[i++];
        }

        while (j < right.length) {
            dest[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

5. Quadrática

O(n²) – Detecção de duplicados

Ideia: dois loops aninhados sobre o mesmo conjunto. Pior caso: nenhum elemento é igual e comparamos praticamente todos com todos.

JavaScript
// O(n²) - Verifica se há duplicados com dois loops

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  // Pior caso: nenhum elemento é igual
  return false;
}

console.log(hasDuplicate([1, 2, 3, 4, 5]));   // false
console.log(hasDuplicate([1, 2, 3, 2, 5]));   // true
Python
# O(n²) - Verifica se há duplicados com dois loops aninhados

def has_duplicate(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    # Pior caso: ~n*(n-1)/2 comparações
    return False


print(has_duplicate([1, 2, 3, 4, 5]))     # False
print(has_duplicate([1, 2, 3, 2, 5]))     # True
Java
// O(n²) - Verifica se há duplicados com dois loops

public class BigON2 {
    public static boolean hasDuplicate(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    return true;
                }
            }
        }
        // Pior caso: nenhum elemento é igual
        return false;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {1, 2, 3, 2, 5};
        System.out.println(hasDuplicate(arr1)); // false
        System.out.println(hasDuplicate(arr2)); // true
    }
}

6. Exponencial

O(2ⁿ) – Subset Sum (Backtracking ingênuo)

Ideia: para cada elemento, decidimos 'usar' ou 'não usar' — isso gera 2ⁿ combinações. Pior caso: precisamos explorar todas as combinações.

JavaScript
// O(2ⁿ) - Subset Sum recursivo

function subsetSumExists(nums, target) {
  function backtrack(index, currentSum) {
    if (currentSum === target) {
      return true;
    }
    if (index === nums.length) {
      return false;
    }

    // Não usar o elemento atual
    if (backtrack(index + 1, currentSum)) {
      return true;
    }

    // Usar o elemento atual
    if (backtrack(index + 1, currentSum + nums[index])) {
      return true;
    }

    return false;
  }

  return backtrack(0, 0);
}

console.log(subsetSumExists([3, 4, 5], 9)); // true
console.log(subsetSumExists([3, 4, 5], 2)); // false
Python
# O(2ⁿ) - Subset Sum recursivo (usa/não usa cada elemento)

def subset_sum_exists(nums, target):
    def backtrack(index, current_sum):
        if current_sum == target:
            return True
        if index == len(nums):
            return False

        # Opção 1: não usar o elemento atual
        if backtrack(index + 1, current_sum):
            return True

        # Opção 2: usar o elemento atual
        if backtrack(index + 1, current_sum + nums[index]):
            return True

        return False

    return backtrack(0, 0)


print(subset_sum_exists([3, 4, 5], 9))  # True
print(subset_sum_exists([3, 4, 5], 2))  # False
Java
// O(2ⁿ) - Subset Sum recursivo

public class BigO2PowerN {
    public static boolean subsetSumExists(int[] nums, int target) {
        return backtrack(nums, target, 0, 0);
    }

    private static boolean backtrack(int[] nums, int target, int index, int currentSum) {
        if (currentSum == target) {
            return true;
        }
        if (index == nums.length) {
            return false;
        }

        // Não usar o elemento atual
        if (backtrack(nums, target, index + 1, currentSum)) {
            return true;
        }

        // Usar o elemento atual
        if (backtrack(nums, target, index + 1, currentSum + nums[index])) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, 5};
        System.out.println(subsetSumExists(nums, 9)); // true
        System.out.println(subsetSumExists(nums, 2)); // false
    }
}

7. Fatorial

O(n!) – Permutações

Ideia: geração de todas as permutações de n elementos. O número de permutações é n!, logo o tempo de execução também cresce como O(n!).

JavaScript
// O(n!) - Gera todas as permutações de um array

function permutations(arr) {
  const result = [];

  function backtrack(path, used) {
    if (path.length === arr.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;

      used[i] = true;
      path.push(arr[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([], new Array(arr.length).fill(false));
  return result;
}

console.log(permutations([1, 2, 3]));
Python
# O(n!) - Gera todas as permutações de um array

def permutations(arr):
    result = []

    def backtrack(path, used):
        if len(path) == len(arr):
            result.append(path.copy())
            return

        for i in range(len(arr)):
            if used[i]:
                continue
            used[i] = True
            path.append(arr[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(arr))
    return result


print(permutations([1, 2, 3]))
Java
// O(n!) - Gera todas as permutações de um array

import java.util.ArrayList;
import java.util.List;

public class BigONFactorial {

    public static List<List<Integer>> permutations(int[] arr) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        boolean[] used = new boolean[arr.length];
        backtrack(arr, new ArrayList<Integer>(), used, result);
        return result;
    }

    // <- everything in one line here
    private static void backtrack(int[] arr, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        if (path.size() == arr.length) {
            result.add(new ArrayList<Integer>(path));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (used[i]) {
                continue;
            }

            used[i] = true;
            path.add(arr[i]);
            backtrack(arr, path, used, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        List<List<Integer>> perms = permutations(arr);
        System.out.println(perms);
        System.out.println("Total: " + perms.size());
    }
}

Dica: use esta página como uma referência rápida ou como material para copiar e colar no Big O Analyzer.