PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Array Operations: Traversal, Insertion, Deletion and Searching (एरे ऑपरेशन्स: ट्रैवर्सल, इंसर्शन, डिलीशन और लीनियर सर्च टाइम) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Arrays support O(1) indexed access and O(n) sequential traversal, whereas inserting or deleting at arbitrary positions requires shifting subsequent elements to preserve memory contiguity, incurring O(n) worst-case time. Linear search scans unsorted elements sequentially in O(n) worst-case time (averaging (n+1)/2 comparisons), while sorted arrays additionally permit O(log n) binary search.
अध्याय सार: एरे में इंडेक्स से एक्सेस O(1) और क्रमिक ट्रैवर्सल O(n) समय में होता है, परंतु मेमोरी की निरंतरता बनाए रखने के लिए बीच में इंसर्शन (Insertion) या डिलीशन (Deletion) करने पर तत्वों को खिसकाना पड़ता है, जिससे अधिकतम O(n) समय लगता है। अव्यवस्थित (Unsorted) एरे में लीनियर सर्च O(n) समय लेती है, जबकि सॉर्टेड एरे में बाइनरी सर्च O(log n) में काम करती है।
Array Operations: Traversal, Insertion, Deletion and Searching: Detailed Notes & Architecture (एरे ऑपरेशन्स: ट्रैवर्सल, इंसर्शन, डिलीशन और लीनियर सर्च टाइम)
1. Array Traversal & Sequential Processing Mechanics (एरे ट्रैवर्सल (Traversal) और क्रमिक प्रोसेसिंग)
[EN] Traversal visits every active element of an array from index 0 through n - 1 exactly once—to print values, compute aggregates, or find extrema. Regardless of element values, traversal always executes n iterations in Theta(n) time and O(1) auxiliary space. Because consecutive elements occupy adjacent bytes, forward linear traversal achieves peak hardware prefetcher and CPU cache utilization compared to pointer-chasing structures.
[HI] ट्रैवर्सल का अर्थ एरे के इंडेक्स 0 से n - 1 तक प्रत्येक सक्रिय तत्व को ठीक एक बार पढ़ना है (जैसे मान प्रिंट करना, योग या अधिकतम खोजना)। एरे में तत्व कुछ भी हों, ट्रैवर्सल हमेशा Theta(n) समय और O(1) अतिरिक्त स्पेस लेता है। लगातार मेमोरी में होने के कारण लीनियर ट्रैवर्सल CPU कैश का सर्वोत्तम उपयोग करता है।
2. Insertion at Index pos: Capacity Check & Right-Shifting Order (एरे में इंसर्शन (Insertion): ओवरफ्लो जाँच व दाईं ओर शिफ्टिंग का सही क्रम)
[EN] Inserting an element at index pos (0 <= pos <= n) first requires verifying that current size n < capacity; otherwise an Overflow error occurs. To open a slot at arr[pos] without overwriting existing data, elements MUST be shifted right starting backwards from i = n - 1 down to pos (arr[i + 1] = arr[i]), followed by arr[pos] = val and n++. Inserting at index 0 requires n shifts (O(n) worst case), whereas appending at index n needs zero shifts (O(1)).
[HI] किसी इंडेक्स pos पर नया तत्व डालने से पहले जाँचा जाता है कि n < capacity हो (अन्यथा Overflow होगा)। डेटा खोए बिना जगह खाली करने के लिए लूप पीछे से (i = n - 1 से pos तक) चलाकर तत्वों को दाईं ओर (arr[i + 1] = arr[i]) खिसकाया जाता है। शुरुआत (इंडेक्स 0) में इंसर्शन में n शिफ्ट (O(n)) लगते हैं, जबकि अंत में जोड़ने पर 0 शिफ्ट (O(1)) लगते हैं।
3. Deletion at Index pos: Underflow Check, Left-Shifting & O(1) Unsorted Trick (एरे से डिलीशन (Deletion): अंडरफ्लो जाँच, बाईं शिफ्टिंग व O(1) ट्रिक)
[EN] Before deleting at valid index pos (0 <= pos < n), the algorithm checks n > 0 to guard against Underflow. To close the gap while preserving relative order, elements shift left starting forward from i = pos up to n - 2 (arr[i] = arr[i + 1]), followed by n--. Deleting index 0 costs n - 1 shifts (O(n)), while deleting the last element costs zero shifts (O(1)). Notably, if element order does NOT matter in an unsorted array, copying arr[pos] = arr[n - 1] and decrementing n deletes in O(1) time.
[HI] किसी इंडेक्स pos से तत्व हटाने से पहले n > 0 जाँचा जाता है (अन्यथा Underflow होगा)। क्रम बनाए रखने के लिए i = pos से n - 2 तक तत्वों को बाईं ओर (arr[i] = arr[i + 1]) खिसकाकर n को 1 घटाया जाता है। पहला तत्व हटाने में n - 1 शिफ्ट (O(n)) लगते हैं, पर यदि क्रम महत्वपूर्ण न हो तो अंतिम तत्व को arr[pos] में रखकर O(1) में डिलीशन किया जा सकता है।
4. Linear Search vs Binary Search & Sentinel Optimization (लीनियर सर्च (Linear Search) बनाम बाइनरी सर्च व सेंटिनल तकनीक)
[EN] Linear (Sequential) Search compares key against arr[0], arr[1], ... until found or reaching n: best case is O(1) at index 0, worst case is O(n) (absent or at index n - 1), and average successful comparisons under uniform probability equal (n + 1) / 2. Linear search works on unsorted arrays and linked lists alike. A classic optimization—Sentinel Linear Search—places key at arr[n] to drop the loop boundary test (i < n) per iteration; sorted arrays allow O(log n) Binary Search.
[HI] लीनियर सर्च key की तुलना क्रमशः arr[0], arr[1]... से करती है: सर्वोत्तम स्थिति O(1), सबसे खराब O(n) और औसत सफल तुलनाएं (n + 1)/2 होती हैं। यह बिना सॉर्ट किए एरे पर भी चलती है। Sentinel Linear Search में एरे के अंत arr[n] में key रखकर हर बार i < n जाँचने की आवश्यकता हटाई जाती है; सॉर्टेड एरे में O(log n) बाइनरी सर्च संभव है।
Syntax, Formula & Technical Example (Array Operations: Traversal, Insertion, Deletion and Searching)
// C Array Insertion & Deletion (n = current size, cap = max capacity)
void insertAt(int a[], int *n, int cap, int pos, int val) {
if (*n >= cap || pos < 0 || pos > *n) return; // Overflow / bounds guard
for (int i = *n - 1; i >= pos; i--) a[i + 1] = a[i]; // Shift right (back-to-front)
a[pos] = val; (*n)++;
}
void deleteAt(int a[], int *n, int pos) {
if (*n <= 0 || pos < 0 || pos >= *n) return; // Underflow / bounds guard
for (int i = pos; i < *n - 1; i++) a[i] = a[i + 1]; // Shift left (front-to-back)
(*n)--;
}
Array Operations: Traversal, Insertion, Deletion and Searching Quick Reference & Comparison Table
| Array Operation | Time Complexity | Shift Count & Edge Condition |
|---|---|---|
| Full Array Traversal | Theta(n) in best, average, and worst cases | Visits all n valid elements sequentially; O(1) extra space |
| Insertion at Index pos | O(1) at end (n); O(n) at beginning (0) | Shifts right from n-1 down to pos; requires n < capacity |
| Deletion at Index pos | O(1) at end (n-1); O(n) at beginning (0) | Shifts left from pos up to n-2; requires n > 0 (not empty) |
| Linear Search | O(1) best; O(n) worst; avg (n+1)/2 comps | Works on unsorted data without preprocessing |
Array Operations: Traversal, Insertion, Deletion and Searching Top 20 Bilingual MCQs with Answers
Q1. What is the worst-case time complexity of inserting a new element at index 0 of a 1D array holding n elements (with free capacity)?
(n तत्वों वाले 1D एरे के इंडेक्स 0 (शुरुआत) पर नया तत्व इंसर्ट करने की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या होती है?)
(A) O(n)
(B) O(log n)
(C) O(1)
(D) O(n log n)
Correct Answer: (A)
[EN] All n existing elements must be shifted one position to the right to vacate index 0, taking O(n) time.
[HI] इंडेक्स 0 खाली करने के लिए सभी n मौजूदा तत्वों को एक-एक स्थान दाईं ओर खिसकाना पड़ता है, जिससे O(n) समय लगता है।
Q2. How many element shifts are needed to delete the element at index 0 from an array currently containing n elements?
(n तत्वों वाले एरे से इंडेक्स 0 का तत्व हटाने (Deletion) के लिए कुल कितनी शिफ्टिंग (Shifts) करनी पड़ती हैं?)
(A) n + 1 shifts
(B) n shifts
(C) n - 1 shifts
(D) 0 shifts
Correct Answer: (C)
[EN] Elements at indices 1 through n - 1 (total n - 1 elements) each shift left by one position.
[HI] इंडेक्स 1 से n - 1 तक के कुल n - 1 तत्वों को एक-एक स्थान बाईं ओर खिसकाना पड़ता है।
Q3. During array insertion at index pos, why must the shifting loop iterate backwards from i = n - 1 down to pos?
(इंडेक्स pos पर इंसर्शन करते समय शिफ्टिंग लूप हमेशा पीछे से (i = n - 1 से pos तक) क्यों चलाया जाता है?)
(A) Iterating forward from pos to n - 1 would overwrite later elements before they are copied
(B) To reduce shift count from O(n) to O(log n)
(C) Because C forbids incrementing loop variables during array writes
(D) To sort the array into descending order automatically
Correct Answer: (A)
[EN] Forward copying a[i+1] = a[i] spreads a[pos] over every subsequent slot, destroying original values.
[HI] आगे से (pos से n - 1) खिसकाने पर a[pos] का ही मान आगे की सभी जगहों पर कॉपी होकर मूल डेटा को नष्ट कर देगा।
Q4. What happens if an array of n = 5 elements {10, 20, 30, 40, 50} mistakenly runs forward insertion at pos = 1: for(i=1; i<5; i++) a[i+1] = a[i]; a[1] = 99;?
(यदि {10, 20, 30, 40, 50} पर pos = 1 के लिए गलत लूप for(i=1; i<5; i++) a[i+1] = a[i]; a[1] = 99; चलाएं, तो एरे क्या बन जाएगा?)
(A) {10, 20, 30, 40, 50, 99}
(B) {10, 99, 20, 20, 20, 20}
(C) {10, 99, 20, 30, 40, 50}
(D) {99, 10, 20, 30, 40, 50}
Correct Answer: (B)
[EN] a[2] gets a[1] (20), then a[3] gets new a[2] (20), propagating 20 through a[5]; finally a[1] = 99.
[HI] a[2] में 20 जाता है, फिर a[3] में a[2] का नया मान 20 जाता है; अंततः पूरा पिछला हिस्सा {20, 20, 20, 20} बन जाएगा।
Q5. What is the best-case time complexity of deleting the LAST element (at index n - 1) of an array of size n?
(n आकार के एरे से सबसे अंतिम तत्व (इंडेक्स n - 1) को हटाने की बेस्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?)
(A) O(1)
(B) O(n)
(C) Theta(n - 1)
(D) O(log n)
Correct Answer: (A)
[EN] Deleting at the end requires zero element shifts—only decrementing the logical size counter n takes O(1).
[HI] अंतिम तत्व हटाने में कोई शिफ्टिंग नहीं करनी पड़ती, केवल लंबाई काउंटर n घटाने से काम O(1) में हो जाता है।
Q6. If maintaining relative element order is NOT required, how fast can you delete an element at arbitrary index pos in an unsorted array?
(यदि अनसॉर्टेड एरे में तत्वों का क्रम बनाए रखना जरूरी न हो, तो किसी भी इंडेक्स pos से डिलीशन कम से कम कितने समय में हो सकता है?)
(A) Still O(n) in all cases
(B) O(n^2) due to re-hashing
(C) O(1) by overwriting arr[pos] = arr[n - 1] and decrementing n
(D) O(log n) using binary partitioning
Correct Answer: (C)
[EN] Swapping or copying the last item arr[n - 1] into arr[pos] fills the hole in constant O(1) time without shifting.
[HI] अंतिम तत्व arr[n - 1] को सीधे arr[pos] पर कॉपी करके n घटाने से बिना शिफ्टिंग के O(1) में डिलीशन हो जाता है।
Q7. For an array of n elements, how many comparisons does Linear Search perform on average when searching for an element known to be present with equal probability at any index?
(यदि कोई तत्व n तत्वों वाले एरे में समान संभावना से कहीं भी मौजूद हो, तो सफल लीनियर सर्च में औसतन कितनी तुलनाएं (Comparisons) होती हैं?)
(A) log2(n)
(B) n^2 / 2
(C) (n + 1) / 2
(D) n / 2 - 1
Correct Answer: (C)
[EN] The sum (1 + 2 + ... + n) / n equals (n + 1) / 2 average comparisons for a uniformly distributed successful linear search.
[HI] 1 से n तक सभी स्थितियों के औसत (1+2+...+n)/n से औसत तुलनाएं (n + 1) / 2 प्राप्त होती हैं।
Q8. What condition causes an Array Overflow error during an insertion operation on a static array of capacity MAX?
(MAX क्षमता वाले स्टैटिक एरे में इंसर्शन के दौरान Overflow की स्थिति कब उत्पन्न होती है?)
(A) When current element count n == 0
(B) When current element count n == MAX
(C) When key is not found in the array
(D) When pos == n - 1
Correct Answer: (B)
[EN] Overflow occurs whenever you attempt to insert into an already full static array (n == MAX).
[HI] जब एरे पहले से पूरी तरह भरा हो (n == MAX) और नया तत्व जोड़ने का प्रयास किया जाए, तब Overflow होता है।
Q9. What is the time complexity of traversing an array of n elements to find both its minimum and maximum values?
(n तत्वों वाले एरे में न्यूनतम और अधिकतम दोनों मान खोजने हेतु ट्रैवर्सल की टाइम कॉम्प्लेक्सिटी क्या होगी?)
(A) O(log n)
(B) O(1)
(C) Theta(n)
(D) O(n^2)
Correct Answer: (C)
[EN] Every element must be inspected at least once when the array is unsorted, requiring Theta(n) comparisons.
[HI] अव्यवस्थित एरे में न्यूनतम व अधिकतम खोजने के लिए हर तत्व को कम से कम एक बार देखना आवश्यक है, अतः Theta(n) समय लगता है।
Q10. Why does inserting a new value into a SORTED array take O(n) worst-case time even if Binary Search finds the position in O(log n)?
(सॉर्टेड एरे में सही स्थान बाइनरी सर्च से O(log n) में मिलने के बावजूद कुल इंसर्शन टाइम O(n) क्यों रहता है?)
(A) Because reading arr[mid] shifts memory addresses
(B) Because up to n elements must still be shifted right to create a physical slot in contiguous memory
(C) Because sorted arrays cannot accept duplicate keys
(D) Because Binary Search itself runs in O(n) on arrays
Correct Answer: (B)
[EN] Total time is O(log n) search + O(n) shifting = O(n), dominated by linear element movement.
[HI] सही जगह O(log n) में मिलने के बाद भी मेमोरी में जगह बनाने हेतु तत्वों को दाईं ओर खिसकाने में O(n) समय लगता है।
Q11. How does Sentinel Linear Search optimize a standard linear search loop?
(Sentinel Linear Search सामान्य लीनियर सर्च लूप को किस प्रकार तेज बनाती है?)
(A) It sorts the array beforehand in O(1) time
(B) It places the target key at arr[n] so the loop omits the i < n boundary comparison on each iteration
(C) It divides the search interval in half at every step
(D) It hashes array indices into a binary tree
Correct Answer: (B)
[EN] Guaranteeing the key exists at arr[n] eliminates half the branch checks per step (only arr[i] != key is tested).
[HI] arr[n] पर लक्ष्य मान रख देने से लूप के भीतर हर बार i < n की सीमा जाँचने की आवश्यकता समाप्त हो जाती है।
Q12. What is the time complexity of appending an element to the end of a dynamic array (like C++ std::vector or Python list) on an amortized basis?
(डायनामिक एरे (जैसे C++ std::vector या Python list) के अंत में तत्व जोड़ने की Amortized टाइम कॉम्प्लेक्सिटी क्या होती है?)
(A) Amortized O(log n)
(B) Amortized O(n)
(C) Amortized O(1)
(D) O(n^2)
Correct Answer: (C)
[EN] Doubling capacity geometrically upon fullness spreads occasional O(n) copy costs across n appends, yielding O(1) amortized per push.
[HI] क्षमता भरने पर आकार दोगुना करने (Geometric Doubling) की रणनीति से प्रति इंसर्शन औसत/Amortized लागत O(1) रहती है।
Q13. Which condition prevents Linear Search from being replaced directly by Binary Search on an array?
(निम्न में से किस स्थिति में एरे पर लीनियर सर्च की जगह सीधे बाइनरी सर्च का उपयोग नहीं किया जा सकता?)
(A) When the array uses 0-based indexing
(B) When the array holds integer values
(C) When array size is a power of two
(D) When the array elements are unsorted
Correct Answer: (D)
[EN] Binary search strictly requires monotonic sorted ordering; on unsorted arrays, only Linear Search works directly.
[HI] बाइनरी सर्च के लिए एरे का सॉर्टेड होना अनिवार्य है; अव्यवस्थित (Unsorted) एरे पर केवल लीनियर सर्च ही काम करती है।
Q14. During array deletion at pos = 3 in an array of n = 6 elements, what is the index of the LAST element copied left?
(6 तत्वों वाले एरे (इंडेक्स 0..5) में pos = 3 हटाने पर बाईं ओर कॉपी होने वाला अंतिम तत्व किस इंडेक्स से आएगा?)
(A) Index 4 (copied into index 5)
(B) Index 5 (copied into index 4)
(C) Index 3 (copied into index 2)
(D) Index 6 (copied into index 5)
Correct Answer: (B)
[EN] The loop for(i = 3; i < 5; i++) a[i] = a[i + 1] runs i=3 (a[3]=a[4]) and i=4 (a[4]=a[5]), copying index 5 last.
[HI] लूप i = 3 से i < 5 तक चलता है, अर्थात अंतिम कॉपी i = 4 पर a[4] = a[5] होती है।
Q15. What happens if an algorithm forgets to check n > 0 before running array deletion at index 0?
(यदि डिलीशन से पहले एरे के खाली होने (n > 0) की जाँच न की जाए तो क्या समस्या आ सकती है?)
(A) Automatic doubling of array capacity
(B) Conversion to a circular linked list
(C) Sorting of negative numbers
(D) Array Underflow / decrementing n to -1 and accessing invalid memory
Correct Answer: (D)
[EN] Deleting from an empty array (n == 0) triggers Underflow and corrupts n (negative length) or reads out-of-bounds memory.
[HI] खाली एरे से डिलीट करने पर Underflow त्रुटि होती है और n ऋणात्मक होकर अमान्य मेमोरी एक्सेस करा सकता है।
Q16. Which statement is NOT true regarding basic Array Operations?
(मूलभूत एरे ऑपरेशन्स के बारे में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) Linear search requires at most n comparisons in the worst case
(B) Inserting an element into the middle of a static array takes O(1) time without shifting elements
(C) Random read access at any valid index takes O(1) time
(D) Deleting from the end of an array takes O(1) time
Correct Answer: (B)
[EN] Middle insertion in a contiguous array requires shifting half the elements on average, taking O(n) linear time—not O(1).
[HI] स्टैटिक एरे के बीच में तत्व जोड़ने पर बाद के तत्वों को खिसकाना पड़ता है, इसलिए यह O(1) नहीं बल्कि O(n) समय लेता है।
Q17. Within Array Operations: Traversal, Insertion, Deletion and Searching, which array operation directly maps to: "Theta(n) in best, average, and worst cases"?
(Array Operations: Traversal, Insertion, Deletion and Searching में कौन सा Array Operation सीधे "Theta(n) in best, average, and worst cases" से संबंधित है?)
(A) Insertion at Index pos
(B) Linear Search
(C) Deletion at Index pos
(D) Full Array Traversal
Correct Answer: (D)
[EN] In Array Operations: Traversal, Insertion, Deletion and Searching, 'Full Array Traversal' handles 'Theta(n) in best, average, and worst cases' (Visits all n valid elements sequentially; O(1) extra space).
[HI] Array Operations: Traversal, Insertion, Deletion and Searching में 'Full Array Traversal' का कार्य/विवरण 'Theta(n) in best, average, and worst cases' (Visits all n valid elements sequentially; O(1) extra space) है।
Q18. Which option accurately describes 'Insertion at Index pos' in Array Operations: Traversal, Insertion, Deletion and Searching?
(Array Operations: Traversal, Insertion, Deletion and Searching के संदर्भ में 'Insertion at Index pos' की सही विशेषता कौन सी है?)
(A) O(1) at end (n-1); O(n) at beginning (0)
(B) O(1) at end (n); O(n) at beginning (0)
(C) O(1) best; O(n) worst; avg (n+1)/2 comps
(D) Theta(n) in best, average, and worst cases
Correct Answer: (B)
[EN] 'Insertion at Index pos' provides 'O(1) at end (n); O(n) at beginning (0)' — key point: Shifts right from n-1 down to pos; requires n < capacity.
[HI] 'Insertion at Index pos' का मुख्य विवरण 'O(1) at end (n); O(n) at beginning (0)' है (Shifts right from n-1 down to pos; requires n < capacity)।
Q19. In Array Operations: Traversal, Insertion, Deletion and Searching, identify the correct parameter for the specification: "O(1) at end (n-1); O(n) at beginning (0)".
(Array Operations: Traversal, Insertion, Deletion and Searching में "O(1) at end (n-1); O(n) at beginning (0)" विवरण किस विकल्प के लिए सही है?)
(A) Linear Search
(B) Full Array Traversal
(C) Insertion at Index pos
(D) Deletion at Index pos
Correct Answer: (D)
[EN] 'Deletion at Index pos' corresponds to 'O(1) at end (n-1); O(n) at beginning (0)' (Shifts left from pos up to n-2; requires n > 0 (not empty)).
[HI] 'Deletion at Index pos' का संबंध 'O(1) at end (n-1); O(n) at beginning (0)' (Shifts left from pos up to n-2; requires n > 0 (not empty)) से है।
Q20. Considering Array Operations: Traversal, Insertion, Deletion and Searching, what key behavior defines 'Linear Search'?
(Array Operations: Traversal, Insertion, Deletion and Searching में 'Linear Search' की मुख्य भूमिका या मान क्या है?)
(A) O(1) at end (n-1); O(n) at beginning (0)
(B) O(1) at end (n); O(n) at beginning (0)
(C) Theta(n) in best, average, and worst cases
(D) O(1) best; O(n) worst; avg (n+1)/2 comps
Correct Answer: (D)
[EN] 'Linear Search' represents 'O(1) best; O(n) worst; avg (n+1)/2 comps' (Works on unsorted data without preprocessing).
[HI] 'Linear Search' का अर्थ/मान 'O(1) best; O(n) worst; avg (n+1)/2 comps' है (Works on unsorted data without preprocessing)।
Array Operations: Traversal, Insertion, Deletion and Searching — Exam FAQs
Q1: Why is insertion or deletion slow in arrays compared to linked lists?
लिंक्ड लिस्ट की तुलना में एरे के शुरुआत या बीच में इंसर्शन और डिलीशन धीमे क्यों होते हैं?
[EN] Because array elements must stay strictly contiguous in RAM; adding or removing at index pos forces O(n) shifting of trailing elements, whereas linked lists merely rewire O(1) pointers once positioned.
[HI] क्योंकि एरे के तत्व मेमोरी में लगातार सटे रहते हैं; बीच में जगह बनाने या भरने के लिए शेष सभी तत्वों को O(n) में खिसकाना पड़ता है।
Q2: If we find the insertion spot in a sorted array using Binary Search (O(log n)), why is overall insertion still O(n)?
यदि सॉर्टेड एरे में इंसर्शन का स्थान बाइनरी सर्च से O(log n) में ढूँढ लें, तो भी कुल इंसर्शन कॉम्प्लेक्सिटी O(n) क्यों मानी जाती है?
[EN] Finding the index takes O(log n) comparisons, but opening a physical slot at that index still requires O(n) element shifts in the worst case; O(log n) + O(n) simplifies asymptotically to O(n).
[HI] स्थान खोजना O(log n) में होता है, परंतु वहाँ नया तत्व रखने के लिए बाकी तत्वों को खिसकाने में O(n) समय लगता है, जो कुल कॉम्प्लेक्सिटी को O(n) बना देता है।
Q3: When is Linear Search preferred over Binary Search?
बाइनरी सर्च की तुलना में लीनियर सर्च का उपयोग कब बेहतर होता है?
[EN] Linear search is preferred when the data is unsorted (avoiding an O(n log n) sort for a single lookup), very small (fits in one cache line), or stored in a linked list lacking O(1) random access.
[HI] जब डेटा अनसॉर्टेड हो, आकार बहुत छोटा हो, या डेटा लिंक्ड लिस्ट में हो जहाँ मध्य तत्व तक O(1) में सीधे नहीं पहुँचा जा सकता।
Post a Comment
Post a Comment