Algorithm Analysis: Time Complexity and Space Complexity Notes in Hindi & English : एल्गोरिदम विश्लेषण: टाइम कॉम्प्लेक्सिटी, स्पेस कॉम्प्लेक्सिटी और दक्षता और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Algorithm Analysis: Time Complexity and Space Complexity (एल्गोरिदम विश्लेषण: टाइम कॉम्प्लेक्सिटी, स्पेस कॉम्प्लेक्सिटी और दक्षता) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: Algorithm analysis evaluates efficiency independently of hardware using Time Complexity (operation growth T(n)) and Space Complexity (fixed overhead plus dynamic auxiliary and recursion stack memory).

अध्याय सार: एल्गोरिदम विश्लेषण हार्डवेयर से स्वतंत्र रहकर टाइम कॉम्प्लेक्सिटी (ऑपरेशन्स की वृद्धि T(n)) और स्पेस कॉम्प्लेक्सिटी (निश्चित मेमोरी तथा अतिरिक्त/रिकर्शन स्टैक मेमोरी) द्वारा दक्षता मापता है।

Algorithm Analysis: Time Complexity and Space Complexity: Detailed Notes & Architecture (एल्गोरिदम विश्लेषण: टाइम कॉम्प्लेक्सिटी, स्पेस कॉम्प्लेक्सिटी और दक्षता)

1. A Priori Mathematical Analysis vs A Posteriori Empirical Testing (ए प्रायोरी (A Priori) विश्लेषण बनाम ए पोस्टेरियोरी (A Posteriori) परीक्षण)

[EN] Algorithm evaluation has two complementary stages. A Posteriori testing implements and runs the program on real hardware, measuring exact milliseconds and bytes consumed—results heavily skewed by CPU speed, OS load, compiler flags, and programming language. In contrast, A Priori analysis evaluates the algorithm mathematically before coding under the idealized Random Access Machine (RAM) model (unit-time primitive arithmetic/comparison steps), expressing operation counts T(n) purely as a function of input size n.

[HI] एल्गोरिदम मूल्यांकन दो तरीकों से होता है: A Posteriori में प्रोग्राम चलाकर वास्तविक मिलीसेकंड और बाइट्स नापे जाते हैं, जो CPU, कंपाइलर व OS पर निर्भर होते हैं। इसके विपरीत, A Priori विश्लेषण कोड चलाने से पहले हार्डवेयर-स्वतंत्र गणितीय मॉडल (RAM मॉडल) पर इनपुट आकार n के फलन T(n) के रूप में ऑपरेशन्स की वृद्धि दर मापता है।

2. Time Complexity: Best, Average, and Worst-Case Guarantees (टाइम कॉम्प्लेक्सिटी: बेस्ट, एवरेज और वर्स्ट केस)

[EN] Time complexity counts elementary steps relative to input size n across three regimes: Best Case (minimum steps on most favorable input, e.g., target at index 0 in Linear Search -> O(1)), Average Case (expected steps across assumed input probability distributions), and Worst Case (maximum steps required for ANY valid input of size n, e.g., absent key in Linear Search -> O(n)). Algorithm engineers prioritize Worst-Case bounds because they furnish a rock-solid upper-limit performance guarantee.

[HI] इनपुट आकार n के लिए तीन स्थितियाँ मापी जाती हैं: बेस्ट केस (सबसे अनुकूल इनपुट पर न्यूनतम समय, जैसे Linear Search में पहला ही तत्व मिल जाना = O(1)), एवरेज केस (औसत संभावित समय), और वर्स्ट केस (सबसे कठिन इनपुट पर अधिकतम समय, जैसे तत्व न मिलना = O(n))। इंजीनियरिंग में वर्स्ट-केस को प्राथमिकता दी जाती है क्योंकि यह समय की पक्की अधिकतम सीमा की गारंटी देता है।

3. Space Complexity: Fixed Part, Variable Part, and Auxiliary Space (स्पेस कॉम्प्लेक्सिटी बनाम ऑक्ज़िलरी (Auxiliary) स्पेस)

[EN] Total Space Complexity S(P) = c + S_p(n) sums a fixed part c (compiled machine code, constants, simple scalar loop counters) and an instance-dependent variable part S_p(n) (arrays, dynamic allocations, and call stack frames). Crucially, exams distinguish Total Space Complexity from Auxiliary Space (extra temporary workspace excluding the input array itself): Merge Sort uses O(n) auxiliary space for merging, whereas In-Place Heap Sort or Insertion Sort needs only O(1) auxiliary space despite holding an O(n) input array.

[HI] कुल स्पेस कॉम्प्लेक्सिटी S(P) = c + S_p(n) में स्थिर भाग c (प्रोग्राम कोड, स्थिरांक) और चर भाग S_p(n) (डायनामिक मेमोरी, रिकर्शन स्टैक) शामिल हैं। परीक्षाओं में Auxiliary Space (इनपुट डेटा को छोड़कर लगने वाली अतिरिक्त अस्थायी मेमोरी) पर विशेष प्रश्न आते हैं: जैसे Merge Sort का ऑक्ज़िलरी स्पेस O(n) है, जबकि In-Place Heap Sort का ऑक्ज़िलरी स्पेस O(1) होता है।

4. Recursion Stack Depth and Amortized Cost Analysis (रिकर्शन स्टैक गहराई और अमॉर्टाइज़्ड (Amortized) विश्लेषण)

[EN] Every active recursive function call pushes an activation frame onto the runtime call stack, consuming memory proportional to the maximum simultaneous recursion depth—NOT total recursive calls! Thus, recursive Binary Search uses O(log n) stack space (vs O(1) iterative), and naive recursive Fibonacci uses O(n) auxiliary stack space despite O(2^n) time complexity. Finally, Amortized Analysis averages occasional costly operations (like doubling a dynamic array in O(n)) over n cheap O(1) insertions to prove O(1) amortized cost per append.

[HI] रिकर्सिव फंक्शन चलने पर कॉल स्टैक में फ्रेम्स बनते हैं, जिनका स्पेस कुल कॉल्स पर नहीं बल्कि अधिकतम रिकर्शन गहराई (Depth) पर निर्भर करता है! इसलिए रिकर्सिव Binary Search O(log n) स्टैक स्पेस लेता है और O(2^n) टाइम वाला नेव रिकर्सिव Fibonacci केवल O(n) स्टैक स्पेस लेता है। वहीं अमॉर्टाइज़्ड विश्लेषण कभी-कभार आने वाले महंगे ऑपरेशन (जैसे डायनामिक ऐरे डबलिंग) का औसत निकालकर प्रति ऑपरेशन O(1) लागत सिद्ध करता है।

Syntax, Formula & Technical Example (Algorithm Analysis: Time Complexity and Space Complexity)

// Loop Step-Count & Iterative vs Recursive Space Comparison
// 1. Triangular Loop: 1 + 2 + ... + n = n(n+1)/2 -> Time: O(n^2), Aux Space: O(1)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        count++;

// 2. Halving Loop: n, n/2, n/4 ... 1 -> Time: O(log n), Aux Space: O(1)
for (int k = n; k > 1; k /= 2)
    ops++;

Algorithm Analysis: Time Complexity and Space Complexity Quick Reference & Comparison Table

Complexity ConceptFormal Measure / RuleConcrete Algorithm Example
A Priori AnalysisHardware-independent operation growth function T(n)Counts loop iterations mathematically before execution
Worst-Case TimeMaximum steps across all valid inputs of size nLinear Search missing key = n comparisons -> O(n)
Auxiliary SpaceTemporary extra memory excluding input structure sizeMerge Sort = O(n); In-place Quick/Heap Sort uses O(log n)/O(1)
Recursion Call StackMemory proportional to maximum tree recursion depthNaive recursive Fibonacci takes O(n) stack space

Algorithm Analysis: Time Complexity and Space Complexity Top 20 Bilingual MCQs with Answers

Q1. Which statement accurately distinguishes A Priori analysis from A Posteriori testing?

(A Priori विश्लेषण और A Posteriori परीक्षण के बीच सही अंतर क्या है?)

(A) Both require running compiled code on Windows

(B) A Priori computes mathematical time/space growth independent of hardware; A Posteriori measures actual runtime on a specific machine

(C) A Posteriori ignores programming language and hardware

(D) A Priori measures seconds on CPU; A Posteriori counts loops mathematically

Correct Answer: (B)

[EN] A Priori relies on RAM-model asymptotic step counting, while A Posteriori benchmarks physical execution.

[HI] A Priori हार्डवेयर-स्वतंत्र गणितीय विश्लेषण है, जबकि A Posteriori मशीन पर चलाकर वास्तविक समय/मेमोरी मापता है।

Q2. What is the precise definition of Auxiliary Space in algorithm analysis?

(एल्गोरिदम विश्लेषण में 'ऑक्ज़िलरी स्पेस' (Auxiliary Space) की सटीक परिभाषा क्या है?)

(A) Space occupied solely by the input array

(B) Extra temporary space used by an algorithm beyond the memory occupied by its inputs

(C) Compiled binary file size on disk only

(D) Total RAM installed on the computer

Correct Answer: (B)

[EN] Total Space Complexity = Input Space + Auxiliary Space (temporary arrays, variables, recursion stack).

[HI] कुल स्पेस = इनपुट स्पेस + ऑक्ज़िलरी स्पेस; अर्थात इनपुट को छोड़कर प्रयुक्त होने वाली अतिरिक्त अस्थायी मेमोरी ही ऑक्ज़िलरी स्पेस है।

Q3. What are the Time Complexity and Auxiliary Space Complexity of this loop: `for(i=1; i<=n; i*=2) { for(j=1; j<=n; j++) sum++; }`?

(इस लूप की टाइम कॉम्प्लेक्सिटी और ऑक्ज़िलरी स्पेस कॉम्प्लेक्सिटी क्या होगी: `for(i=1; i<=n; i*=2) for(j=1; j<=n; j++) sum++;`?)

(A) Time: O(n^2), Auxiliary Space: O(1)

(B) Time: O(n log n), Auxiliary Space: O(1)

(C) Time: O(n^2 log n), Auxiliary Space: O(log n)

(D) Time: O(log n), Auxiliary Space: O(n)

Correct Answer: (B)

[EN] Outer loop doubles `i` (log2(n) iterations); inner loop runs n times per outer step -> O(n log n) time, scalar vars -> O(1) space.

[HI] बाहरी लूप log2(n) बार और आंतरिक लूप हर बार n बार चलता है, अतः टाइम O(n log n) तथा केवल साधारण वेरिएबल होने से स्पेस O(1) होगा।

Q4. What is the Time Complexity of the triangular nested loop `for(i=1; i<=n; i++) for(j=1; j<=i; j++) x++;`?

(नेस्टेड लूप `for(i=1; i<=n; i++) for(j=1; j<=i; j++) x++;` की टाइम कॉम्प्लेक्सिटी क्या है?)

(A) O(n)

(B) O(n log n)

(C) O(2^n)

(D) O(n^2)

Correct Answer: (D)

[EN] Total iterations = 1 + 2 + ... + n = n(n+1)/2 = (n^2 + n)/2, which is O(n^2).

[HI] कुल पुनरावृत्तियाँ 1 + 2 + ... + n = n(n+1)/2 होंगी, जिसकी एसिम्प्टोटिक कॉम्प्लेक्सिटी O(n^2) है।

Q5. Compare the Auxiliary Space Complexity of Iterative Binary Search vs Recursive Binary Search on an array of size n.

(n आकार के ऐरे पर इटरेटिव Binary Search बनाम रिकर्सिव Binary Search की ऑक्ज़िलरी स्पेस कॉम्प्लेक्सिटी क्या होती है?)

(A) Iterative uses O(log n); Recursive uses O(1)

(B) Both use O(n)

(C) Iterative uses O(1); Recursive uses O(log n) due to call stack frames

(D) Both use O(1)

Correct Answer: (C)

[EN] Recursive Binary Search keeps up to log2(n) active call frames on the stack simultaneously, whereas iterative uses 3 scalar pointers.

[HI] रिकर्सिव Binary Search में कॉल स्टैक की गहराई log2(n) तक जाती है (O(log n)), जबकि इटरेटिव में केवल O(1) स्पेस लगता है।

Q6. What is the Auxiliary Space Complexity of naive recursive Fibonacci `fib(n) = fib(n-1) + fib(n-2)`?

(नेव रिकर्सिव Fibonacci `fib(n) = fib(n-1) + fib(n-2)` की ऑक्ज़िलरी स्पेस कॉम्प्लेक्सिटी क्या होती है?)

(A) O(1)

(B) O(n) (because maximum call stack depth is n, even though time is O(2^n))

(C) O(2^n)

(D) O(log n)

Correct Answer: (B)

[EN] Left branches finish and pop stack frames before right branches allocate new frames, capping active depth at n.

[HI] कॉल स्टैक पर एक समय में अधिकतम गहराई n फ्रेम्स तक ही जाती है (भले ही टाइम O(2^n) हो), अतः स्पेस O(n) है।

Q7. What is the Time Complexity of a divisor-checking loop `for(int i = 2; i * i <= n; i++)`?

(लूप `for(int i = 2; i * i <= n; i++)` की टाइम कॉम्प्लेक्सिटी क्या होती है?)

(A) O(√n)

(B) O(n)

(C) O(log n)

(D) O(n^2)

Correct Answer: (A)

[EN] The condition `i * i <= n` terminates as soon as `i > √n`.

[HI] शर्त `i * i <= n` तब रुकती है जब `i`, √n से बड़ा हो जाए, इसलिए कॉम्प्लेक्सिटी O(√n) है।

Q8. Why isn't Time Complexity normally expressed in milliseconds or seconds in textbooks?

(पाठ्यपुस्तकों और परीक्षाओं में टाइम कॉम्प्लेक्सिटी को मिलीसेकंड या सेकंड में क्यों नहीं मापा जाता?)

(A) Because Big-O converts seconds into bytes

(B) Actual seconds vary wildly by CPU speed, RAM, compiler, and background OS processes

(C) Because computers cannot measure milliseconds accurately

(D) Because seconds only measure space complexity

Correct Answer: (B)

[EN] Counting primitive operations as a function of n creates a universal hardware-independent benchmark.

[HI] वास्तविक सेकंड CPU, कंपाइलर और OS लोड पर बदलते रहते हैं, जबकि ऑपरेशन्स की संख्या हर मशीन पर समान रहती है।

Q9. What is the Auxiliary Space Complexity of Merge Sort vs In-Place Insertion Sort on an n-element array?

(n तत्वों वाले ऐरे पर Merge Sort बनाम In-Place Insertion Sort का ऑक्ज़िलरी स्पेस कितना होता है?)

(A) Both use O(1)

(B) Merge Sort uses O(n); Insertion Sort uses O(1)

(C) Merge Sort uses O(1); Insertion Sort uses O(n)

(D) Both use O(n log n)

Correct Answer: (B)

[EN] Standard array Merge Sort allocates a temporary O(n) buffer during merging, whereas Insertion Sort swaps in place with O(1) extra space.

[HI] Merge Sort मर्जिंग के लिए O(n) अतिरिक्त ऐरे लेता है, जबकि Insertion Sort स्थान पर ही सॉर्ट करके केवल O(1) अतिरिक्त स्थान लेता है।

Q10. In Space Complexity `S(P) = c + S_p`, what does `c` represent?

(स्पेस कॉम्प्लेक्सिटी समीकरण `S(P) = c + S_p` में `c` किसे दर्शाता है?)

(A) Recursion call stack depth

(B) Fixed space independent of input size (program instructions, constants, simple scalar variables)

(C) Dynamic heap allocations

(D) Total network bandwidth

Correct Answer: (B)

[EN] Fixed part `c` stays constant across all input sizes, while `S_p` scales with instance characteristics.

[HI] `c` प्रोग्राम के निर्देशों, स्थिरांकों और साधारण वेरिएबल्स का स्थिर भाग है जो इनपुट आकार पर निर्भर नहीं करता।

Q11. Why do software engineers prioritize Worst-Case Time Complexity over Best-Case Time Complexity?

(सॉफ्टवेयर इंजीनियर बेस्ट-केस की तुलना में वर्स्ट-केस टाइम कॉम्प्लेक्सिटी को अधिक महत्व क्यों देते हैं?)

(A) Best-case is impossible to calculate mathematically

(B) Worst-case guarantees the algorithm will never perform slower than that upper bound on any valid input

(C) Worst-case is always equal to O(1)

(D) Best-case requires twice as much memory

Correct Answer: (B)

[EN] Real-time and production systems require strict guarantees against worst-case inputs and timeouts.

[HI] वर्स्ट-केस यह पक्की गारंटी देता है कि किसी भी कठिन इनपुट पर भी एल्गोरिदम इससे अधिक समय नहीं लेगा।

Q12. What is the Amortized Time Complexity per insertion when appending n elements to a dynamic array that doubles capacity upon filling?

(जब एक डायनामिक ऐरे भरने पर अपनी क्षमता दोगुनी करता है, तो n तत्व जोड़ने पर प्रति तत्व अमॉर्टाइज़्ड (Amortized) टाइम कॉम्प्लेक्सिटी क्या होगी?)

(A) O(log n) amortized

(B) O(1) amortized

(C) O(n^2) amortized

(D) O(n) amortized

Correct Answer: (B)

[EN] Total copies across n appends form a geometric sum 1 + 2 + 4 + ... + n < 2n, yielding O(2n / n) = O(1) per append.

[HI] क्षमता दोगुनी होने पर कुल कॉपी ऑपरेशन्स 2n से कम रहते हैं, जिसे n से भाग देने पर प्रति ऑपरेशन O(1) अमॉर्टाइज़्ड लागत आती है।

Q13. What is the Time Complexity of `int k = n; while(k > 1) { k = k / 3; }`?

(`int k = n; while(k > 1) { k = k / 3; }` की टाइम कॉम्प्लेक्सिटी क्या है?)

(A) O(n / 3)

(B) O(n)

(C) O(√n)

(D) O(log n)

Correct Answer: (D)

[EN] Dividing `k` by 3 each step runs log3(n) steps, which is asymptotically O(log n).

[HI] हर चरण में मान 3 से भाग होने पर लूप log3(n) बार चलेगा, जो O(log n) के बराबर है।

Q14. What is the Recursive Call Stack Space Complexity of computing Factorial `fact(n) = n * fact(n-1)`?

(रिकर्सिव फैक्टोरियल `fact(n) = n * fact(n-1)` की स्टैक स्पेस कॉम्प्लेक्सिटी क्या होती है?)

(A) O(1)

(B) O(log n)

(C) O(n)

(D) O(n^2)

Correct Answer: (C)

[EN] It creates a linear chain of n nested stack frames before reaching base case `n == 0`.

[HI] बेस केस तक पहुँचने से पहले स्टैक पर n सक्रिय कॉल्स जमा होती हैं, अतः स्पेस O(n) है।

Q15. If an algorithm executes `5n^2 + 100n + 2500` basic operations, which single term dominates its asymptotic Time Complexity?

(यदि किसी एल्गोरिदम में कुल `5n^2 + 100n + 2500` ऑपरेशन्स हों, तो उसकी टाइम कॉम्प्लेक्सिटी क्या मानी जाएगी?)

(A) O(2500)

(B) O(100n)

(C) O(n^2)

(D) O(n^3)

Correct Answer: (C)

[EN] For large n, the highest-degree term n^2 dominates lower-order terms and constant multipliers.

[HI] बड़े n के लिए सबसे उच्च घात वाला पद n^2 ही प्रभावी रहता है (अतः O(n^2))।

Q16. Which statement is NOT true about Algorithm Complexity Analysis?

(एल्गोरिदम कॉम्प्लेक्सिटी विश्लेषण के बारे में कौन सा कथन असत्य (NOT true) है?)

(A) Auxiliary space excludes the memory occupied by the input dataset itself

(B) A Priori analysis assumes an idealized machine independent of CPU clock speed

(C) Iterative Binary Search achieves O(1) auxiliary space

(D) Naive recursive Fibonacci takes O(2^n) auxiliary space because it makes O(2^n) function calls

Correct Answer: (D)

[EN] Recursive Fibonacci takes O(2^n) time, but only O(n) space because stack frames are popped before sibling subtrees run.

[HI] नेव रिकर्सिव Fibonacci का टाइम O(2^n) होता है, पर कॉल स्टैक की अधिकतम गहराई n होने के कारण उसका ऑक्ज़िलरी स्पेस केवल O(n) होता है।

Q17. Within Algorithm Analysis: Time Complexity and Space Complexity, which complexity concept directly maps to: "Hardware-independent operation growth function T(n)"?

(Algorithm Analysis: Time Complexity and Space Complexity में कौन सा Complexity Concept सीधे "Hardware-independent operation growth function T(n)" से संबंधित है?)

(A) A Priori Analysis

(B) Auxiliary Space

(C) Recursion Call Stack

(D) Worst-Case Time

Correct Answer: (A)

[EN] In Algorithm Analysis: Time Complexity and Space Complexity, 'A Priori Analysis' handles 'Hardware-independent operation growth function T(n)' (Counts loop iterations mathematically before execution).

[HI] Algorithm Analysis: Time Complexity and Space Complexity में 'A Priori Analysis' का कार्य/विवरण 'Hardware-independent operation growth function T(n)' (Counts loop iterations mathematically before execution) है।

Q18. Which option accurately describes 'Worst-Case Time' in Algorithm Analysis: Time Complexity and Space Complexity?

(Algorithm Analysis: Time Complexity and Space Complexity के संदर्भ में 'Worst-Case Time' की सही विशेषता कौन सी है?)

(A) Hardware-independent operation growth function T(n)

(B) Temporary extra memory excluding input structure size

(C) Memory proportional to maximum tree recursion depth

(D) Maximum steps across all valid inputs of size n

Correct Answer: (D)

[EN] 'Worst-Case Time' provides 'Maximum steps across all valid inputs of size n' — key point: Linear Search missing key = n comparisons -> O(n).

[HI] 'Worst-Case Time' का मुख्य विवरण 'Maximum steps across all valid inputs of size n' है (Linear Search missing key = n comparisons -> O(n))।

Q19. In Algorithm Analysis: Time Complexity and Space Complexity, identify the correct parameter for the specification: "Temporary extra memory excluding input structure size".

(Algorithm Analysis: Time Complexity and Space Complexity में "Temporary extra memory excluding input structure size" विवरण किस विकल्प के लिए सही है?)

(A) A Priori Analysis

(B) Recursion Call Stack

(C) Worst-Case Time

(D) Auxiliary Space

Correct Answer: (D)

[EN] 'Auxiliary Space' corresponds to 'Temporary extra memory excluding input structure size' (Merge Sort = O(n); In-place Quick/Heap Sort uses O(log n)/O(1)).

[HI] 'Auxiliary Space' का संबंध 'Temporary extra memory excluding input structure size' (Merge Sort = O(n); In-place Quick/Heap Sort uses O(log n)/O(1)) से है।

Q20. Considering Algorithm Analysis: Time Complexity and Space Complexity, what key behavior defines 'Recursion Call Stack'?

(Algorithm Analysis: Time Complexity and Space Complexity में 'Recursion Call Stack' की मुख्य भूमिका या मान क्या है?)

(A) Temporary extra memory excluding input structure size

(B) Memory proportional to maximum tree recursion depth

(C) Hardware-independent operation growth function T(n)

(D) Maximum steps across all valid inputs of size n

Correct Answer: (B)

[EN] 'Recursion Call Stack' represents 'Memory proportional to maximum tree recursion depth' (Naive recursive Fibonacci takes O(n) stack space).

[HI] 'Recursion Call Stack' का अर्थ/मान 'Memory proportional to maximum tree recursion depth' है (Naive recursive Fibonacci takes O(n) stack space)।

Algorithm Analysis: Time Complexity and Space Complexity — Exam FAQs

Q1: What is the difference between Space Complexity and Auxiliary Space?

स्पेस कॉम्प्लेक्सिटी और ऑक्ज़िलरी स्पेस में क्या अंतर है?

[EN] Auxiliary Space is only the extra temporary workspace (temp arrays, stack frames) allocated during execution, whereas Total Space Complexity equals Input Space + Auxiliary Space.

[HI] ऑक्ज़िलरी स्पेस केवल अतिरिक्त अस्थायी मेमोरी है, जबकि कुल स्पेस कॉम्प्लेक्सिटी में इनपुट डेटा की मेमोरी और ऑक्ज़िलरी स्पेस दोनों शामिल होते हैं।

Q2: Why does naive recursive Fibonacci use O(n) space instead of O(2^n) space?

नेव रिकर्सिव Fibonacci में O(2^n) कॉल्स होने पर भी स्पेस केवल O(n) क्यों लगता है?

[EN] Memory on the call stack is reused! The left recursive branch finishes and releases its frames before the right branch runs, so active stack depth never exceeds `n`.

[HI] क्योंकि कॉल स्टैक की मेमोरी पुनः उपयोग होती है—बाएँ हिस्से के कॉल समाप्त होकर मेमोरी मुक्त कर देते हैं, अतः एक साथ अधिकतम n फ्रेम ही स्टैक पर रहते हैं।

Q3: Why is Worst-Case Time Complexity usually reported instead of Average-Case?

अक्सर एवरेज-केस के बजाय वर्स्ट-केस कॉम्प्लेक्सिटी क्यों बताई जाती है?

[EN] Average-case requires assuming a specific probability distribution over inputs (often unrealistic), while worst-case guarantees a hard upper limit on execution time for every possible input.

[HI] एवरेज-केस के लिए इनपुट वितरण का अनुमान लगाना पड़ता है, जबकि वर्स्ट-केस हर संभावित इनपुट के लिए समय की पक्की ऊपरी सीमा की गारंटी देता है।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)