Øv med flashcards — Algoritmer, kjøretid og asymptotisk notasjon

Kapittel 1 · TDT4120

1 / 16

16 kort

Formel

Store O (øvre grense)

Formel

O (g (n)) = {f (n) : \exists c, n_{0} > 0, 0 \leq f (n) \leq c g (n) \forall n \geq n_{0}}

$f$ vokser ikke raskere enn $g$ utover en konstant faktor, fra et punkt $n_{0}$ og utover. Beskriver en øvre grense på kjøretiden.

Tips: bruk piltastene for å bla og mellomrom/Enter for å snu kortet.