Asymptotic analysis of an algorithm (Big Oh Notation)

Asymptotic analysis :-

Asymptotic analysis of an algorithm represents a mathematical function (boundary) of its run-time performance. Generally, asymptotic notations are used to represent time complexity. We can use different types of asymptotic notations to represent complexity of an algorithm like:-

किसी अल्गोरिथम के अनंतस्पर्शीय विश्लेषण में एक गणितीय फलन (सीमा) के द्वारा अल्गोरिथम के रन टाइम प्रदर्शन को दर्शाया जाता है। सामान्यतः असमटोटिक नोटेशन का प्रयोग टाइम कॉम्प्लेक्सिटी को ज्ञात करने के लिए किया जाता है। किसी अल्गोरिथम की कॉम्प्लेक्सिटी को दर्शाने के लिए अलग-अलग प्रकार के असमटोटिक नोटेशन का प्रयोग किया जाता है जैसे:-

O- Big Oh (upper bound)

Ω- Big omega (lower bound)

θ- Big theta (tight bound)

in addition इसके अतिरिक्त

o- Little Oh

ω- Little omega

O-Big Oh :-

The asymptotic notation Ο(n) is used to represent the upper bound of an algorithm's running time. It calculates worst case time complexity of an algorithm.

O(n) अल्गोरिथम के रनिंग टाइम के upper bound (उच्चक) को दर्शाता है। यह अल्गोरिथम की वर्स्ट केस टाइम कॉम्प्लेक्सिटी की गणना करता है।

for a function f(n)

किसी फंक्शन f(n) के लिए

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) <= c.g(n) for all n > n0 }

Here, function g(n) is an upper bound for function f(n) because It increases faster than f(n).

यहाँ, फंक्शन f(n) के लिए फंक्शन g(n) एक upper bound है क्योंकि फंक्शन g(n), f(n) की तुलना में तेजी से वृद्धि करता है।

Ω- Big omega :-

The asymptotic notation Ω(n) is used to represent the lower bound of an algorithm's running time. It calculates best case time complexity of an algorithm.

Ω(n) अल्गोरिथम के रनिंग टाइम के lower bound (निम्नक) को दर्शाता है। यह अल्गोरिथम की बेस्ट केस टाइम कॉम्प्लेक्सिटी की गणना करता है।

for a function f(n)

किसी फंक्शन f(n) के लिए

Ω(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) >= c.g(n) for all n > n0 }

Here, function g(n) is a lower bound for function f(n) because It increases slower than f(n).

यहाँ, फंक्शन f(n) के लिए फंक्शन g(n) एक lower bound है क्योंकि फंक्शन g(n), f(n) की तुलना में धीमी गति से वृद्धि करता है।

θ- Big theta :-

The asymptotic notation θ(n) is used to represent the upper bound and the lower bound of an algorithm's running time. It calculates average case time complexity of an algorithm.

θ(n) अल्गोरिथम के रनिंग टाइम के upper bound (उच्चक) एवं lower bound (निम्नक) दोनों को दर्शाता है। यह अल्गोरिथम की एवरेज केस टाइम कॉम्प्लेक्सिटी की गणना करता है।

for a function f(n)

किसी फंक्शन f(n) के लिए

θ(f(n)) = { g(n) : there exists c1,c2 > 0 and n0 such that f(n) >= c1.g(n) and f(n) <= c2.g(n) for all n > n0 }

Here, function c2.g(n) is an upper bound and c1.g(n) is a lower bound for function f(n) because c2.g(n) increases faster than f(n) and c1.g(n) increases slower than f(n).

यहाँ, फंक्शन f(n) के लिए फंक्शन c2.g(n) एक upper bound है क्योंकि यह f(n) की तुलना में तीव्र गति से वृद्धि करता है जबकि c1.g(n) एक lower bound है क्योंकि यह, f(n) की तुलना में धीमी गति से वृद्धि करता है।