• (grafo non orientato) $0 \leq m \leq \frac{n(n-1)}{2}$
• (grafo orientato): $0 \leq m \leq n^2$
• numero di inversioni: $0\leq N_{inv}\leq \frac{n(n-1)}{2}$
• altezza albero binario (k = numero foglie): $h(k)\geq \lceil \log_2 k \rceil$
• albero binario completo: $2^h \leq n \leq 2^{h+1}-1 \rarr h \sim \log_2 n$
• alberi binari degeneri con n nodi: $2^{n-1}$
• qualunque algoritmo confronti e scambi esegue nel caso peggiore almeno $n \log_2 n+o(n \log_2 n)$ confronti per ordinare una sequenza di n dati
• alberi 2-3:
  • $2^h \leq n \leq 3^h$
  • → si ricava l'altezza: $\log_3 n \leq h \leq \log _2 n$ → $\Theta(\log n)$
  • operazioni $\Theta(\log n)$
• albero 2-3-4:
  • numero di dati: $2^{h+1}-1 \leq n \leq 4^{h+1}-1$
  • altezza: $\Theta(\log n)$
  • altezza: $h\geq \log_4 n + \log_4 3-1$
• altezza di un albero RB con n valori:
  • altezza: $\Theta(\log n)$ (massimo il doppio dell'altezza di un 2-3-4)
  • altezza: $\log_4(n+1)-1\leq h \leq 2\log_2(n+1)-2$
• equazione di ricorrenza divide et impera: $T(n) =mT\Big(\frac{n}{a}\Big) +f(n)$