📈 Big-O जटिलता

drag the slider — every mode updates live

खुद आज़माएँ: N स्लाइडर को 4 से खींचकर 4k तक ले जाइए, और हर पड़ाव पर run experiment दबाइए। N=4 पर हर बार एक जैसी दिखती है; N=4k पर O(n²) वाली बार बाकी सबको बौना बना देती है। यही फ़ासला है जिसके बारे में Big-O आपको आगाह करना चाहता है।

यह क्यों मायने रखता है

अगले 10 अध्यायों में आपको जितने भी डेटा स्ट्रक्चर मिलेंगे, हर एक किसी एक लागत के बदले दूसरी लागत चुकाता है। ऐरे O(1) में पढ़ते हैं पर डालने में O(n) लगाते हैं। हैश टेबल O(1) में ढूँढ लेती हैं पर उनमें कोई क्रम नहीं होता। संतुलित पेड़ (balanced trees) थोड़ी constant-factor रफ़्तार छोड़कर बदले में O(log n) का worst-case पक्का करते हैं। इन शब्दों का कोई मतलब तब तक नहीं बनता जब तक आपने महसूस न कर लिया हो कि N बढ़ने पर यह फ़र्क़ दिखता कैसा है।

यही इस अध्याय का मक़सद है। अभी कोड नहीं — बस वह वक्र (curve)।

Big-O आख़िर नापता क्या है

किसी एल्गोरिथ्म द्वारा किए गए बुनियादी ऑपरेशनों की संख्या, इनपुट के आकार के एक फलन (function) के रूप में, worst case में, constants और lower-order terms को नज़रअंदाज़ करते हुए।

इसमें तीन भार उठाने वाले हिस्से हैं:

• इनपुट के आकार के एक फलन के रूप में। यह एक वक्र है, कोई एक संख्या नहीं। "इसमें कितनी तुलनाएँ लगीं?" — इसका कोई जवाब नहीं; पर "इसमें N चीज़ों के लिए कितनी तुलनाएँ लगीं?" — इसका जवाब है।
• Worst case। 1,000 चीज़ों में रैखिक खोज (linear search) शायद पहली ही कोशिश में लक्ष्य पा ले। पर अगर आप वह कोड प्रोडक्शन में भेज रहे हैं, तो आपको सबसे बुरी स्थिति के लिए तैयारी करनी होगी — तीनों हज़ार, यानी पूरे 1,000 को जाँचना।
• Constants और lower-order terms को नज़रअंदाज़ करना। 3n + 5 और n — दोनों O(n) हैं। N बढ़ने पर constants की आवाज़ दब जाती है। बेंचमार्क के लिए ये मायने रखते हैं; पर asymptotic आकार के लिए नहीं।

O, Θ, Ω — तीन सीमाएँ (bounds)

इंजीनियर रोज़मर्रा की बातचीत में "Big-O" कह देते हैं, पर पाठ्यपुस्तकें तीन अलग नोटेशनों में फ़र्क़ करती हैं। ये किसी फलन की वृद्धि (growth) पर अलग-अलग सीमाएँ बताते हैं।

Asymptotic नोटेशन

O(f(n)) — ऊपरी सीमा (upper bound)। T(n) = O(f(n)) का मतलब है कि T ज़्यादा से ज़्यादा उतनी तेज़ी से बढ़ता है जितनी f। "इससे ज़्यादा खर्च नहीं।"

Ω(f(n)) — निचली सीमा (lower bound)। T(n) = Ω(f(n)) का मतलब है कि T कम से कम उतनी तेज़ी से बढ़ता है जितनी f। "इससे कम खर्च नहीं।"

Θ(f(n)) — सटीक सीमा (tight bound)। O(f(n)) और Ω(f(n)) दोनों। "ठीक f के अनुपात में खर्च।"

एक ठोस उदाहरण — merge sort

O(n log n) — इसका worst case n log n से बुरा नहीं होता। सच पर ढीला: यह O(n²), O(n³), … भी है — कोई भी ऊपरी सीमा सही ठहरती है।

Ω(n log n) — इसका best case कम से कम n log n है (किसी भी तुलना-आधारित सॉर्ट की यह निचली सीमा एक information-theoretic तर्क से सिद्ध होती है)।

Θ(n log n) — सटीक कथन: merge sort ठीक n log n के दर्जे का है, न इससे तेज़ न इससे धीमा।

रिवीज़न के वक़्त यह क्यों मायने रखता है: जब कोई पाठ्यपुस्तक Θ(n) लिखती है, तो वह दावा कर रही है कि एल्गोरिथ्म n से ऊपर और नीचे दोनों तरफ़ बंधा है — यह O(n) से कहीं ज़्यादा मज़बूत कथन है। एक बाइनरी सर्च O(log n) है (worst case), Ω(1) है (best case — पहली ही जाँच में मेल), और कुल मिलाकर Θ(log n) नहीं है — पर worst case में Θ(log n) है। नोटेशन चुनने से पहले तय कर लीजिए कि आप किस केस की बात कर रहे हैं।

Best, worst, average

ऊपर बताई गई सीमाओं के साथ-साथ यह भी मायने रखता है कि आप कौन-सा इनपुट नापते हैं:

• Worst case — वह इनपुट जो काम को अधिकतम कर दे। जब आप बिना किसी शर्त के "Big-O" कहते हैं, तो डिफ़ॉल्ट यही होता है।
• Best case — वह इनपुट जो काम को न्यूनतम कर दे। Quicksort का best case Θ(n log n) है; उसका worst Θ(n²) है।
• Average case — किसी इनपुट वितरण (distribution) पर अपेक्षित काम। हैश टेबल लुकअप average में O(1) है पर worst में O(n)।
• Amortized — एक ही डेटा स्ट्रक्चर पर ऑपरेशनों के एक क्रम के औसत के रूप में। डायनैमिक ऐरे का append amortized O(1) है, क्योंकि कभी-कभार होने वाले O(n) resize की कीमत पिछले n सस्ते append चुका देते हैं। प्रमाणों के लिए ऐरे और हीप वाले अध्याय देखिए।

चार्ट को कैसे पढ़ें

हर बार एक चिर-परिचित ऑपरेशन है जो लंबाई N के एक ही इनपुट ऐरे पर चल रहा है:

श्रेणियाँ (classes)

O(1) lookup arr[42] — एक CPU ऑपरेशन, N चाहे कुछ भी हो

O(log n) binary search — हर कदम पर खोज-क्षेत्र आधा करना

O(n) find max — हर तत्व को एक बार छूना

O(n log n) merge sort — n तत्व, हर एक log n merge स्तरों से होकर गुज़रता है

O(n²) find all pairs — हर (i,j) संयोजन

दोनों बार का क्या मतलब है

predicted इस N पर फ़ॉर्मूले का मान (asymptote)

actual असली ऐरे पर एल्गोरिथ्म चलाने से निकला असली ऑपरेशन-काउंट

बार x-अक्ष पर log scale इस्तेमाल करती हैं। O(1) = 1 ऑपरेशन और O(n²) = 8 million ऑपरेशन को एक ही चार्ट में बिठाने का यही एकमात्र तरीक़ा है। log अक्ष पर दूरियों को आँख से आँकना भ्रामक होता है — संख्याएँ पढ़िए।

छोटे-N का जाल

N = 4 पर बार आँख से अलग-अलग नहीं दिखतीं। O(1) = 1, O(n²) = 6। छह तो "लगभग कुछ नहीं" है। यही वजह है कि शुरुआती दौर के इंजीनियर ऐसा O(n²) कोड लिख देते हैं जो टेस्टिंग में चलता है पर प्रोडक्शन में पिघल जाता है — टेस्ट फ़िक्स्चर में 10 पंक्तियाँ थीं, प्रोड टेबल में 1 करोड़ हैं।

N = 1024 तक पहुँचते-पहुँचते:

1024 तत्वों की कीमत क्या है

O(1) 1 ऑपरेशन

O(log n) ~10 ऑपरेशन

O(n) 1,024 ऑपरेशन

O(n log n) ~10,240 ऑपरेशन

O(n²) 523,776 ऑपरेशन

वही एल्गोरिथ्म, वही मशीन — फिर भी इनके बीच परिमाण के पाँच कोटि (five orders of magnitude) का अंतर है।

और गहराई में

कुछ ठोस नियम (rules of thumb) जिन पर आप बाक़ी पाठ्यक्रम में टिके रहेंगे:

• अगर इनपुट पर एक अकेला लूप दिखे, तो आपके पास कम से कम O(n) है।
• अगर नेस्टेड लूप दिखें और दोनों इनपुट को छू रहे हों, तो आप O(n²) पर हैं।
• अगर हर कदम पर काम आधा हो जाए (रिकर्शन, बाइनरी सर्च, संतुलित-पेड़ में उतरना), तो यह O(log n) है।
• तुलना-आधारित डेटा को सॉर्ट करना O(n log n) है — आम स्थिति में आप इससे बेहतर नहीं कर सकते (information-theoretic निचली सीमा)।
• हैशिंग लूप को O(1) expected में समेट देती है — पर इसकी क़ीमत क्रम और worst-case गारंटियों को छोड़ देने में चुकानी पड़ती है।

अब — चलिए असली डेटा स्ट्रक्चरों की ओर।