Big O Notation: A-Level CS में क्या चाहिए

Big O नोटेशन हर प्रमुख A-level कंप्यूटर विज्ञान स्पेक (AQA, OCR, Edexcel) में दिखता है और यह बहुत सारे छात्रों को भ्रमित करता है—न कि इसलिए कि गणित कठिन है, बल्कि इसलिए कि वे इसे कभी असली कोड से जुड़ा नहीं देखते। यह इस बारे में एक व्यावहारिक मार्गदर्शन है कि आपको क्या जानना है और परीक्षा के सवालों का जवाब लंबे-चौड़े उत्तर दिए बिना कैसे दें।

Big O वास्तव में क्या मापता है

Big O यह बताता है कि एक एल्गोरिथ्म का चलने का समय (या मेमोरी का उपयोग) कैसे बढ़ता है जब इनपुट का आकार, आमतौर पर n कहा जाता है, बड़ा होता है। यह सेकंड में स्टॉपवॉच का माप नहीं है। यह वृद्धि दर का वर्णन करने का एक तरीका है ताकि आप हार्डवेयर से अलग एल्गोरिथ्म की तुलना कर सकें।

जब आप O(n) लिखते हैं, तो आप कह रहे हैं: अगर मैं इनपुट को दोगुना कर दूं, तो काम लगभग दोगुना हो जाता है। O(n²) का मतलब इनपुट को दोगुना करने से काम लगभग चार गुना हो जाता है। परीक्षार्थी इस संबंध को पहचानना चाहते हैं, ऑपरेशन की सटीक गिनती नहीं।

जो जटिलताएं आपको पता होनी चाहिए

A-level के लिए, ये हैं वो जो बार-बार आती हैं:

• O(1) – constant time। किसी array एलिमेंट को index से एक्सेस करना: arr[5]। array कितना बड़ा हो, कोई फर्क नहीं पड़ता।
• O(log n) – logarithmic। सॉर्ट की गई लिस्ट पर binary search। हर कदम बचे हुए सर्च स्पेस को आधा कर देता है।
• O(n) – linear। एक लिस्ट के जरिए एक ही लूप, जैसे linear search जो हर आइटम को एक बार चेक करता है।
• O(n log n) – linearithmic। Merge sort और quicksort (average case) यहां आते हैं।
• O(n²) – quadratic। एक ही डेटा पर नेस्टेड लूप, जो exactly वही है जो bubble sort, insertion sort और selection sort करते हैं।
• O(2ⁿ) – exponential। Memoisation के बिना naive recursive Fibonacci। यह जल्दी बुरा हो जाता है।

आपको pseudocode देखने और इसमें से कौन सी है यह एक नजर में कहने में सक्षम होना चाहिए, क्योंकि यही ज्यादातर परीक्षा में आता है।

कोड को जटिलता के लिए पढ़ना

वह तरीका जो हर बार काम करता है: लूप को गिनें और देखें कि वे n से कैसे संबंधित हैं।

# O(n) - एक लूप, एक पास
for i in range(n):
    print(i)

# O(n^2) - नेस्टेड लूप, दोनों n से जुड़े हैं
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - सर्च स्पेस हर iteration में आधा हो जाता है
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

एक नेस्टेड लूप जहां इनर लूप की रेंज n पर निर्भर करती है, वह अभी भी O(n²) है, भले ही यह थोड़ा अलग दिखे (for j in range(i) की बजाय for j in range(n) — वह अभी भी quadratic है कुल मिलाकर, बस एक constant factor फर्क के साथ)।

ऐसे लूप के लिए सावधान रहें जो n पर बिल्कुल निर्भर नहीं करते। एक लूप जो input साइज से अलग हमेशा 10 बार चलता है, वह O(1) है, भले ही एक लूप मौजूद हो। परीक्षार्थी इसे छुपे हुए तरीके से डालना पसंद करते हैं।

सामान्य सॉर्टिंग एल्गोरिथ्म और उनका Big O

यह एक पसंदीदा परीक्षा विषय है क्योंकि यह एक साथ दो स्पेक को जोड़ता है: सॉर्टिंग एल्गोरिथ्म और जटिलता।

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Merge sort की consistency (best और worst case में समान जटिलता) एक सवाल में explicitly mention करने लायक है जो पूछता है कि बड़े डेटासेट के लिए आप bubble sort पर इसे क्यों चुनते हैं। Bubble sort का best case O(n) सिर्फ एक early-exit optimization के साथ लागू होता है जब एक पास में कोई swaps नहीं होते — यह विवरण mention करें अगर आप इसे लाते हैं, क्योंकि कुछ exam boards इसकी अपेक्षा करते हैं।

जहां छात्र अंक खोते हैं

सबसे बड़ा: लिख