Asimptotik qeydlər funksiyaların böyümə sürətini müqayisə etməyə imkan verir. Sabit vuruqları və kiçik hədləri atıb əsasını saxlayırıq.

Üç qeyd

  • O(g) — yuxarı hədd: f ən çox g qədər sürətlə böyüyür.
  • Ω(g) — aşağı hədd: f ən azı g qədər sürətlə böyüyür.
  • Θ(g) — dəqiq hədd: f və g eyni sürətlə böyüyür.
f(n) iki hədd arasında
f(n) iki hədd arasında

3n² + 5n + 7 funksiyası O(n²), Ω(n²) və deməli Θ(n²)-dır. O həm də O(n³)-dür, lakin bu zəif hədddir.

Formal tərif

  • f(n) = O(g(n)), əgər elə c > 0 və n0 var ki, bütün n ≥ n0 üçün f(n) ≤ c · g(n).
  • f(n) = Ω(g(n)), əgər elə c > 0 və n0 var ki, bütün n ≥ n0 üçün f(n) ≥ c · g(n).
  • f(n) = Θ(g(n)), əgər həm O, həm Ω doğrudur.

«=» burada tam bərabərlik deyil, «sinfə daxildir» deməkdir.