Asymptotická notace
Nechť f,g : N^M+, pak
► f(n) G (D(g(n)), pokud existují c G       r?o G N taková, že pro všechna n > r?o, f (n) < c • g"(r?).
► f(n) G ft(g"(r?)), pokud existují c G      r?o G N taková, že pro všechna r? > r?o, f (n) > c ■ s{n)-
► f(n) G e(g(n)), pokud je f(n) v <9(g(n)) i v Q(g{n)).
► f(n) G o(g(n)), pokud lim
f(n)
0.
► f(n) G u;(g(n)), pokud lim
g(n) g(n)
0.
f(n)
Příklad - korektnost, složitost
l function mult(y, z) if z = 0 then
return 0 else if z is odd then
return mult(2y, [z/2\ +y) else
return mult(2y, LZ/2J)
Příklad - korektnost, složitost
1 function mult (y z)
x <- 0
while z > 0 do
if z /s oc/oř then
|_ x <- x + y
y ^2y . z <- Lz/2j
return x
Příklad - korektnost, složitost
l function divide (y, z)
r <- y q <- 0 w <— z
while w < y do w <■ while w > z do
w \_w/2 if w < r then
r <— r — w q^q+1
return (q, r)
2i/i/