लागत कैसे बढ़ती है

Big O मापता है कि इनपुट बढ़ने पर लागत कैसे बढ़ती है। स्थिर गुणांक नहीं — दर। N=100 पर दोनों एल्गोरिदम 'कुछ मिलीसेकंड' में चल सकते हैं, लेकिन N=10,000 पर यदि एक O(N) में और दूसरा O(N²) में चलता है तो वे 10,000 गुना भिन्न हो सकते हैं।

सामान्य जटिलता वर्ग

O(1) — स्थिर। N की परवाह किए बिना समान लागत। उदाहरण: कुंजी द्वारा हैश टेबल लुकअप, इंडेक्स द्वारा ऐरे एक्सेस, स्टैक पुश/पॉप। N को दोगुना करने से कुछ नहीं बदलता।

O(log N) — लघुगणकीय। प्रत्येक चरण शेष कार्य को आधा कर देता है। उदाहरण: सॉर्ट किए गए ऐरे में बाइनरी सर्च, गेम इंजन में BVH स्पेशियल क्वेरी, बैलेंस्ड बाइनरी ट्री ऑपरेशन्स। N=1,000,000 पर: log₂(1,000,000) ≈ 20 चरण।

O(N) — रैखिक। लागत इनपुट के साथ बढ़ती है। उदाहरण: सूची का रैखिक स्कैन, फ़ाइल पढ़ना, संग्रह में आइटम गिनना। N=10,000 पर: 10,000 ऑपरेशन्स।

O(N log N) — रैखिक-लघुगणकीय। लगभग रैखिक, थोड़ा खराब। उदाहरण: मर्ज सॉर्ट, कुशल शॉर्टेस्ट-पाथ एल्गोरिदम (हीप के साथ डिज्क्स्ट्रा)। N=10,000 पर: ~133,000 ऑपरेशन्स।

O(N²) — द्विघातीय। लागत तेज़ी से बढ़ती है। उदाहरण: list.contains() को उसी सूची पर लूप के अंदर कॉल करना, बबल सॉर्ट, नेटिव ऑल-पेयर्स तुलना। N=1,000 पर: 1,000,000 ऑपरेशन्स। N=10,000 पर: 100,000,000 ऑपरेशन्स।

O(2^N) — एक्सपोनेंशियल। किसी भी सार्थक स्तर पर उपयोग करने योग्य नहीं। उदाहरण: ब्रूट-फोर्स कॉम्बिनेटोरिक्स, सभी सबसेट्स खोजना। N=30 पर: 1,000,000,000 से अधिक ऑपरेशन्स।

वह स्केल जो इसे दृश्यमान बनाता है

N=10 तुलनाएँ:
O(N):   10
O(N²):  100
अनुपात:  10x

N=1,000 तुलनाएँ:
O(N):   1,000
O(N²):  1,000,000
अनुपात:  1,000x

N=10,000 तुलनाएँ:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

N=10 पर अंतर लगभग नज़र नहीं आता। N=10,000 पर O(N²) एल्गोरिदम 10,000 गुना धीमा चलता है। यही कारण है कि MOAD-0001 दशकों तक अदृश्य रहा: 1993 में इसके ग्राफ़ में केवल 50 नोड्स थे। 2020 तक वही कोड 50,000 नोड्स वाले डिपेंडेंसी ग्राफ़ पर चल रहा था।

तीन ऑपरेशनों को वर्गीकृत करें

कंक्रीट ऑपरेशनों पर जटिलता वर्ग लागू करें। हर एक के लिए मुख्य प्रश्न: N बढ़ने पर कितने ऑपरेशन लगते हैं?

सही कोड, गलत ग्रोथ कर्व

O(N²) समय में चलने वाला सही कोड O(N) कोड के समान परिणाम देता है। टेस्ट पास हो जाते हैं। आउटपुट मेल खाता है। कोई अपवाद नहीं उठता। दोष ग्रोथ कर्व में छिपा रहता है।

यह गुण O(N²) दोषों को सेडिमेंटरी बनाता है: वे कार्यशील कोड के अंदर जम जाते हैं और केवल तब दिखाई देते हैं जब N एक सीमा से आगे बढ़ जाता है। कोड नहीं बदला। उसके आसपास की दुनिया बदल गई।

MOAD-0001: द सेडिमेंटरी डिफेक्ट

सबसे आम उदाहरण: ग्राफ ट्रैवर्सल लूप के अंदर visited = []।

visited = []
for node in graph:
if node not in visited:  # O(N) scan each call
visited.append(node)
process(node)

प्रत्येक not in visited कॉल 0 से len(visited)-1 तक आइटम्स को स्कैन करता है। N कॉल्स × औसत N/2 स्कैन की गई आइटम्स = कुल O(N²)। समाधान: एक लाइन। [BLOCK_TYPE cost_of_silence/hidden_quadratic]

```python [BLOCK_TYPE cost_of_silence/hidden_quadratic]

visited = set() # O(1) सदस्यता परीक्षण [BLOCK_TYPE cost_of_silence/hidden_quadratic]

for node in graph: [BLOCK_TYPE cost_of_silence/hidden_quadratic]

if node not in visited: # O(1) हैश लुकअप [BLOCK_TYPE cost_of_silence/hidden_quadratic]

visited.add(node) [BLOCK_TYPE cost_of_silence/hidden_quadratic]

process(node) [BLOCK_TYPE cost_of_silence/hidden_quadratic]

Same behavior. Same output. Same tests passing. The growth rate changes from O(N²) to O(N). At N=1,000: 1,000× faster. At N=10,000: 10,000× faster.
### Why Hamming's Era Seeded This
In early Java & C, ArrayList (dynamic array) was the default sequential container. Sets existed but were not idiomatic — developers reached for what was familiar. A 1993 graph traversal at N=50 ran in microseconds with `visited = []`. That code entered version control, got copied, got wrapped in libraries, got shipped in package managers. By 2020, the same pattern ran on dependency graphs with 50,000 nodes.
The code was correct in 1993. It became expensive when the world around it changed. Hamming's era seeded this class of defect by never naming the growth-rate question.

Diagnose & Fix

Apply the diagnosis: find the O(N²) pattern, identify the fix.

कौन-से नामकरण परिवर्तन

बिग O के नाम से पहले, प्रोग्रामर सिर्फ़ 'यह धीमी चल रही है' देखते थे। वे प्रोफाइल करते थे। वे कोड फिर लिखते थे। लेकिन वे पैटर्न सिखा नहीं पाते थे — वे केवल उदाहरणों की ओर इशारा कर सकते थे। बिना नाम के पैटर्न प्रसारित नहीं हो सकता।

बिग O के नाम आने के बाद, एक सीनियर इंजीनियर कह सकता था 'यह O(N²) है, इसे सेट से बदलो' और एक जूनियर इंजीनियर समझ सकता था, लागू कर सकता था, और आगे सिखा सकता था। नाम ने पैटर्न को ज्ञान की एक हस्तांतरणीय इकाई बना दिया।

हैमिंग ने अन्य क्षेत्रों में इस गतिशीलता को जाना। उन्होंने बताया कि 1960 के दशक में 'स्पैगेटी कोड' नाम देने से समुदाय एक ऐसे दोष वर्ग को पहचान, चर्चा और अंततः मिटा सका जिसे हर कोई अनुभव कर चुका था लेकिन किसी ने नाम नहीं दिया था। यही तंत्र जटिलता वर्गों पर भी लागू होता है।

Unhamming हैमिंग द्वारा छोड़े गए शब्दावली को जोड़ता है: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N)। ये नाम आपको कोड में वृद्धि वक्र देखने, स्केल पर प्रदर्शन का अनुमान लगाने, और सुधारों को सटीकता से संप्रेषित करने देते हैं। ये हैमिंग के मौलिक परीक्षण को पूरा करते हैं: टिकाऊ, और क्षेत्र के अधिकांश शेष भाग को उत्पन्न करने वाले। [TITLE who_coined_big_o/]

संख्या सिद्धांत से कंप्यूटर विज्ञान तक

Big O notation की उत्पत्ति कंप्यूटर विज्ञान में नहीं हुई थी। यह शुद्ध गणित — विशेष रूप से संख्या सिद्धांत — में Donald Knuth द्वारा एल्गोरिदम के लिए इसे अपनाने से 74 वर्ष पहले उत्पन्न हुई थी।

Paul Bachmann, 1894

जर्मन गणितज्ञ Paul Bachmann ने 1894 में अपनी पुस्तक Die Analytische Zahlentheorie (Analytic Number Theory) में O notation प्रस्तुत की। उन्हें एक संक्षिप्त तरीके की आवश्यकता थी जिससे यह व्यक्त किया जा सके कि एक राशि किसी अन्य राशि से किसी स्थिर गुणांक तक अधिक तेजी से नहीं बढ़ती। 'f(n) = O(g(n))' लिखने का अर्थ था: f अधिकतम g जितनी तेजी से बढ़ती है। इससे संख्या सिद्धांतकार सटीक स्थिरांकों को ट्रैक किए बिना सन्निकटनों में त्रुटि पदों के बारे में तर्क कर सकते थे।

Bachmann लूप्स, डेटा संरचनाओं या निष्पादन समय के बारे में नहीं सोच रहे थे। वे अभाज्य संख्याओं के वितरण — विशेष रूप से Prime Number Theorem में त्रुटि पदों — के बारे में सोच रहे थे।

Edmund Landau, 1909

एक अन्य जर्मन गणितज्ञ Edmund Landau ने 1909 में अपनी पुस्तक Handbuch der Lehre von der Verteilung der Primzahlen (Handbook on the Distribution of Prime Numbers) में इस संकेतन को लोकप्रिय बनाया। Landau ने संबंधित संकेतन o (little-o) भी प्रस्तुत किया और इस परिवार के असम्प्तोटिक प्रतीकों का इतना व्यापक उपयोग किया कि यह परिवार Bachmann-Landau notation या सरल रूप में Landau notation के नाम से जाना जाने लगा।

छह दशकों तक, O notation पूरी तरह से गणित में रहा। किसी भी प्रोग्रामर ने इसके बारे में नहीं सोचा।

डोनाल्ड नुथ, 1968 और 1976

डोनाल्ड नुथ ने इस संकेतन को कंप्यूटर विज्ञान में अनुवादित किया। द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग (खंड 1, 1968) में, नुथ ने एल्गोरिदम के रनिंग टाइम का वर्णन करने के लिए O संकेतन का उपयोग किया — यह बाखमैन के उपकरण को एक नए क्षेत्र में प्रत्यारोपित करने जैसा था। वे एल्गोरिदम विश्लेषण में इसे व्यवस्थित रूप से लागू करने वाले पहले व्यक्ति थे।

1976 में, नुथ ने SIGACT News में 'Big Omicron and Big Omega and Big Theta' शीर्षक से एक छोटा पेपर प्रकाशित किया। उन्होंने निचली सीमाओं के लिए ओमेगा (Ω) और सटीक सीमाओं के लिए थीटा (Θ) प्रस्तुत किया, जिससे कंप्यूटर विज्ञान में आज उपयोग होने वाली तीन-प्रतीक शब्दावली पूरी हुई। उन्होंने इन प्रतीकों के उपयोग को क्षेत्र में मानकीकृत करने की भी वकालत की — यह एक जानबूझकर किया गया मानकीकरण था जिसने इसके अपनाने को तेज़ किया।

1980 के दशक की शुरुआत तक, Big O हर एल्गोरिदम पाठ्यपुस्तक में दिखने लगा। 1990 के दशक तक, यह साक्षात्कार की मानक शब्दावली बन चुका था।

74-वर्षीय यात्रा

1894 — बाखमैन ने संख्या सिद्धांत में O प्रस्तुत किया
1909 — लैंडाउ ने O, o और पूरे संकेतन परिवार को लोकप्रिय बनाया
1953 — हैमिंग बेल लैब्स में शोध शुरू करते हैं (कभी बिग ओ को CS टूल के रूप में नहीं सीखते)
1968 — नुथ TAOCP Vol. 1 में एल्गोरिदम विश्लेषण के लिए O का प्रयोग करते हैं
1976 — नुथ Omega और Theta जोड़ते हैं; मानकीकरण के लिए तर्क देते हैं
1980s — Big O सभी CS पाठ्यक्रमों में शामिल हो जाता है
1993 — MOAD-0001 प्रोडक्शन कोड में सेडिमेंट लेयर बनाता है
1995 — हैमिंग अपने कोर्स का अंतिम संस्करण पढ़ाते हैं; कभी Big O को कवर नहीं करते
2026 — MOAD-0001 1,000+ ओपन-सोर्स प्रोजेक्ट्स में पाया जाता है

Bachmann का टूल 74 वर्षों तक शुद्ध गणित में रहा, हर गणितज्ञ को दिखता रहा लेकिन हर प्रोग्रामर के लिए अदृश्य रहा। Knuth ने इसे ट्रांसप्लांट किया। Hamming — उसी युग में काम करते हुए, उसी कंप्यूटिंग समुदाय के साथ सहयोग करते हुए — इसे कभी अपने कोर्स का हिस्सा नहीं बना पाए।

Why Knuth's Standardization Mattered

Knuth के 1976 पेपर ने Omega और Theta को पेश करने के अलावा भी कुछ किया। उन्होंने तर्क दिया कि क्षेत्र को सुसंगत नोटेशन की आवश्यकता है, और असंगत नोटेशन वास्तव में हानिकारक था। विभिन्न पाठ्यपुस्तकों में O का अर्थ अलग-अलग लिया जाता था — कभी ऊपरी सीमा के रूप में, कभी अनुमान के रूप में, कभी यह स्पष्ट किए बिना कि स्थिरांक मायने रखते हैं या नहीं। Knuth ने इसे साफ किया।

यह Hamming के पैटर्न-नामकरण गतिशीलता को नोटेशन पर ही लागू करने जैसा था। Knuth द्वारा प्रतीकों को मानकीकृत करने से पहले, इंजीनियर पाठ्यपुस्तकों, पेपर्स या टीमों के बीच जटिलता दावों को सटीक रूप से संप्रेषित नहीं कर पाते थे। मानकीकरण के बाद, 'यह O(N log N) में चलता है' का अर्थ ठीक एक ही था, चाहे कोई भी कहे।

Knuth ने अनौपचारिक अनुवाद भी दिया: 'O(f(n)) का अर्थ है कि रनिंग टाइम f(n) का अधिकतम एक स्थिरांक गुना है, पर्याप्त रूप से बड़े n के लिए।' यह व्याख्या — ऊपरी सीमा, स्थिरांक गुणक तक, बड़े इनपुट के लिए — हर प्रोग्रामर द्वारा सीखी जाने वाली मानक अंतर्ज्ञान बन गई।