Algoritmlar samaradorligini tahlil qilish

Таъриф: t(n) функция O(g(n)) га тегишли бўлиб, t(n) ∈ O(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни

• Таъриф: t(n) функция O(g(n)) га тегишли бўлиб, t(n) ∈ O(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни
• бўлади, агар баъзи бир мусбат c ва манфий
• бўлмаган бутун n0 мавжуд бўлса. Mасалан:

Таъриф: t(n) функция Ω(g(n)) га тегишли бўлиб, t(n) ∈ Ω(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни

• Таъриф: t(n) функция Ω(g(n)) га тегишли бўлиб, t(n) ∈ Ω(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни
• бўлади, агар баъзи бир мусбат c ва манфий
• бўлмаган бутун n0 мавжуд бўлса. Mасалан:

Таъриф: t(n) функция Ө(g(n)) га тегишли бўлиб, t(n) ∈ Ө(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни

• Таъриф: t(n) функция Ө(g(n)) га тегишли бўлиб, t(n) ∈ Ө(g(n)) каби белгиланади. Агар барча n лар учун t(n) функция g(n) нинг қандайдир доимий карралиси билан юқоридан чегараланган бўлса, яъни
• бўлади, агар баъзи бир мусбат c ва манфий
• бўлмаган бутун n0 мавжуд бўлса. Mасалан:

Асимптотик Нотацияларни ўз ичига олган фойдали хусусият

• Асимптотик ифодаларнинг расмий таърифларидан фойдаланиб, уларнинг умумий хусусиятларини исботлашимиз мумкин (қаранг 7-муаммо бир нечта оддий мисоллар учун ушбу бўлим машқларида). Қуйидаги теорема, хусусан, кетма-кет бажариладиган иккита қисмни ўз ичига олган алгоритмларни таҳлил қилишда фойдалидир.

Нотацияларда Ω ва (-) белгиларидан ҳам фойдаланиш мумкин.