Tamanho importa

Valores Assintóticos

Que número é maior: \(\binom{n}{3}\) ou \(n^2\)?

Nem sempre conseguimos valores exatos em uma contagem. E nem sempre expressões exatas são tão informativas assim.

Responda rápido: existem mais subconjuntos de 3 elementos ou pares ordenados em um conjunto?

Uma estimativa útil (para \(n\) suficientemente grande…): \[\left(\frac{n}{k}\right)^k\leq \binom{n}{k}\leq\left(\frac{en}{k}\right)^k.\]

Pergunta: escolhemos uniformemente ao acaso um grafo (rotulado) com 30 vértices, e contamos o número de circuitos com 5 vértices. Quantos ciclos esperamos encontrar?