Asimptotske klase. Asimptotska relacija ekvivalencije

#fax #math #a1 [deo poglavlja "limes funkcije"]

Def. Neka su funkcije,

Oznaka Definicija

Def. su funkcije, . Tada
tako da i

Svojstva

Stav. su funkcije, . Tada
tako da i

Za važi:

Stav. Svojstva :

Svojstva . Veza između i

Stav. je relacija ekvivalencije

Stav.
Stav.

Primer:
,
ako i

Osnovni limesi na jeziku i

kod važe

Asimptotsko ponašanje algoritma