Properties of Big “O” Notation

Properties of Big “O” Notation – किसी भी “O” Notation की कुछ General विशेषताऐं होती हैं जिन्हें हम निम्नानुसार समय  सकते हैं-

• किसी भी Algorithm को जब Mathematically Represent किया जाता है तो उसके जितने भी Constant Factors होते हैं उन्हें Ignore किया जा सकता है। उदाहरण के लिए यदि किसी Array में N Data Elements हैं और कोई Algorithm Array के सभी Elements को Process करता है जबकि N का मान 0 से अधिक है तो इस Algorithm की Complexity O(n) होगी। यानी

For All N > 0 , N f is O(n)

उदाहरण के लिए xz² व yn² दोनों की Complexity समान है और दोनों को “O” Notation के रूप में O(n²) ही लिखेंगे।

• n की Higher Power (उच्चतम घातांक) Lower Power (निम्नतम घातांक) से अधिक तेजी से Grow होता है। यानी

            200n³ + 50n² + 20n¹ + 544n⁰                                       का “O” Notation O(n³) होगा।

इस उदाहरण में देख सकते हैं कि फलन n⁰ भी है और n³ भी लेकिन इसका “O” Notation O(n³) ही है क्योंकि ये उच्चतम घातांक है और अन्‍य सभी घातांकों की तुलना में इसका मान बहुत ही ज्यादा तेजी से Grow होगा और ये अन्‍य घातांको की तुलना में बहुत ही ज्यादा Operations को Represent करेगा, जिससे अन्‍य घातांकों के Operations की संख्‍या को Ignore किया जा सकता है।

• कुल Operations के योग के बढने की दर वही होती है जो सबसे अधिक Growth Term की होती है। यानी यदि किसी Algorithm में

an³ + bn⁴ + cn² + dn¹

Operations होते हैं तो इस Algorithm की Complexity bn⁴ के बढने की दर के बराबर होगी। यानी इस Algorithm के Operations को “O” Notation के रूप में यदि लिखा जाए तो O(n⁴) ही लिखना होगा।

• यदि फलन f फलन g की तुलना में अधिक तेजी से Grow होता है और फलन g फलन h की तुलना मे अधिक तेजी से Grow होता है तो फलन f फलन h की तुलना में भी अधिक तेजी से बढता है।

• किसी फलन के Upper Bound (अधिकतम Operations की संख्‍या) का किसी अन्‍य फलन से गुणा किया जाता है तो प्राप्त होने वाला मान Upper Bound (अधिकतम Operations की संख्‍या) को Represent करता है। जैसे

IF f is O( g ) and h is O( r ) then fh is O( gr )

उदाहरण के लिए

IF f is O( n² ) and h is O(  log n ) then fh is O( n² log n )

• Exponential फलन Power फलन की तुलना में अधिक तेजी से बढते हैं। जैसे

n^k is O(bⁿ), जबकि b के सारे मान 1 से बडे हों और k का मान 0 या 0 से बडा हो। यानी

n^k is O(bⁿ), For all b > 1 ; k >= 0

उदाहरण के लिए

n⁴ is O(2ⁿ), and n⁴ is O(exp(n))

• Logarithms Powers की तुलना में बहुत ही धीमी गति से बढते हैं। जैसे

Log_b n is O(n^k) for all b > 1 ; k > 0

उदाहरण के लिए log₂ n is O(n^0.5)

किसी Algorithm को Analyze करते समय हमारे सामने दो सबसे बडी समस्याऐं होती हैं-

CPU TIME

Input / Output

इन दोनों के बारे में हम आगे आने वाले Posts में विस्‍तार से Discuss करेंगे। (Properties of Big “O” Notation)