एल्गोरिदम की वृद्धि और आसिम्प्टोटिक सीमाएँ

पहले तय करें कि क्या गिन रहे हैं

दो प्रोग्राम एक ही उत्तर देते हुए अलग मात्रा में काम कर सकते हैं। एल्गोरिदम-विश्लेषण बताता है कि इनपुट के आकार के साथ संसाधनों का उपयोग कैसे बदलता है। केवल लूप गिनकर स्टॉपवॉच का समय नहीं निकलता। आप लागत-मॉडल चुनना, सीमित लूप गिनना, O, Ω और Θ का अंतर तथा इनपुट की स्थिति को वृद्धि की सीमा से अलग रखना सीखेंगे।

पूर्वज्ञान: C चर, आरंभिक मानों वाले ऐरे, वैध इंडेक्स, लूप, फ़ंक्शन और कुल रिकर्सिव कॉल बनाम एक साथ सक्रिय फ़्रेम का अंतर। n चुने हुए इनपुट तत्वों की संख्या है, उनका योग या सबसे बड़ा मान नहीं। ऐरे की capacity भंडारण है; तार्किक लंबाई n बताती है कि कॉल कितने तत्व इस्तेमाल करती है। अगले खोज और sorting पाठ यही शब्दावली इस्तेमाल करेंगे। यह शुरुआती परिचय है, पूरी complexity, recurrence हल करना या सभी एल्गोरिदम के lower-bound प्रमाण नहीं।

लागत-मॉडल (cost model) तय करता है कि काम की कौन-सी घटना गिनेंगे। जैसे कुंजी-तुलना, ऐरे-तत्व तक पहुँचना या किसी विशेष लूप-बॉडी का चलना। हर जगह वही क्रिया गिनें। एक “लूप iteration” अपने-आप एक मशीन निर्देश नहीं है। सामान्य निश्चित आकार के C पूर्णांकों में साधारण तुलना, असाइनमेंट और अंकगणित को स्थिर-लागत मानते हैं। मनमाने बड़े पूर्णांक, डिस्क या नेटवर्क के लिए दूसरा मॉडल चाहिए।

समय-लागत फलन f(n) में एल्गोरिदम और इनपुट-स्थिति का नियम, दोनों बताएँ। आकार n के सभी अनुमत इनपुट पर अधिकतम लागत worst case है; न्यूनतम best case है। Average case के लिए बताना होगा कि इनपुट किस प्रायिकता-वितरण से चुने जाते हैं; वह सामान्यतः best और worst की साधारण औसत नहीं है।

शिक्षण की सीमा और आसिम्प्टोटिक परिवार

नीचे चलने वाले उदाहरण जानबूझकर केवल 0 <= n <= 8 स्वीकारते हैं ताकि हर इंडेक्स और गणना सुरक्षित रहे। केवल निश्चित सीमित दायरे पर आसिम्प्टोटिक वृद्धि-श्रेणियों में अर्थपूर्ण अंतर नहीं कर सकते। जब हम बड़े होते n की वृद्धि बताते हैं, तो वही लूप-पैटर्न पर्याप्त capacity और गिनती दर्शा सकने वाले काउंटर के साथ कार्यान्वयनों के परिवार में मानते हैं। वास्तविक CAP=8 प्रोग्राम को उसकी सीमा से बाहर नहीं चलाते।

गणित और सुरक्षित प्रोग्राम का काम अलग है: छोटे सटीक ट्रेस बताते हैं कि लूप क्या गिनता है; प्रतीकात्मक सूत्र बड़े आकार वाले पैटर्न को बताता है। “अनंत n” तर्क की नकल के लिए इनपुट-जाँच न हटाएँ। संकेतन इस्तेमाल करने से C integer overflow या संसाधन-सीमा समाप्त नहीं होती।

ऊपरी, निचली और दोनों ओर से कसी सीमा

f(n) गैर-ऋणात्मक लागत हो और तुलना-फलन g(n) पर्याप्त बड़े पूर्णांक n पर धनात्मक हो। नीचे सभी स्थिरांक धनात्मक और n से स्वतंत्र हैं। सीमा-बिंदु n0 भी निश्चित है।

• f, O(g) है: ऊपरी सीमा। ऐसे C और n0 हों कि हर n >= n0 पर 0 <= f(n) <= C*g(n) हो।
• f, Ω(g) है: निचली सीमा। ऐसे c और n0 हों कि हर n >= n0 पर 0 <= c*g(n) <= f(n) हो।
• f, Θ(g) है: दोनों ओर से कसी सीमा। ऐसे c, C और n0 हों कि हर n >= n0 पर 0 <= cg(n) <= f(n) <= Cg(n) हो।

यानी Θ(g) के लिए O(g) और Ω(g), दोनों चाहिए। इसका अर्थ f(n) बिल्कुल g(n) हो, सभी इनपुट समान समय लें या वास्तविक समय से स्थिरांक मिट जाएँ, नहीं है। n0 से पहले के सीमित छोटे आकार अलग व्यवहार कर सकते हैं।

O ऊपरी सीमा है; उसका tight होना आवश्यक नहीं। रैखिक फलन O(n का वर्ग) भी हो सकता है। यह सही लेकिन Θ(n) से कम जानकारी देता है। Ω चुने हुए लागत-फलन की निचली सीमा है, best case का दूसरा नाम नहीं। O भी worst case का दूसरा नाम नहीं। पहले best, worst, किसी निश्चित इनपुट-पैटर्न या स्पष्ट औसत को चुनें, फिर उस फलन की सीमा निकालें।

हल सहित ट्रेस 1: सीमा का अनुमान नहीं, प्रमाण दें

मानें किसी सटीक मॉडल में पूर्णांक n >= 0 के लिए f(n) = 3n + 2 है। n >= 1 पर:

3n <= 3n + 2 <= 5n।

c = 3, C = 5 और n0 = 1 चुनें। ये स्थिरांक f के Θ(n) होने का प्रमाण हैं। केवल ऊपरी असमानता O(n), और निचली Ω(n) साबित करती है। n >= 1 पर n <= n का वर्ग भी है, इसलिए यही f, O(n का वर्ग) भी है। इससे उसकी tight वृद्धि द्विघात नहीं हो जाती।

यह Θ(n का वर्ग) क्यों नहीं है? अनुपात f(n)/(n का वर्ग) = 3/n + 2/(n का वर्ग), n बढ़ने पर जितना चाहें उतना छोटा हो जाता है। कोई निश्चित धनात्मक c, सभी पर्याप्त बड़े n पर c*n का वर्ग को f(n) से नीचे नहीं रख सकता। खासकर O(n का वर्ग) होने से आवश्यक द्विघात निचली सीमा नहीं मिलती। ये इसी f के कथन हैं, मापे हुए कुछ समय-नमूनों के नहीं।

C11 के तीन पूरे सीमित उदाहरण

पहला फ़ंक्शन पहले n तत्व जोड़कर तत्व-पठन की गिनती रखता है। दूसरा i < j वाली इंडेक्स-जोड़ी गिनता है, कुंजी-तुलना नहीं। तीसरा बार-बार पूर्णांक आधा करने की पुनरावृत्तियाँ गिनता है। काउंटर चुनी घटनाएँ मापते हैं, हर CPU निर्देश नहीं। तीनों में लूप कितनी बार चलेगा, यह डेटा के मान पर निर्भर नहीं है।

#include <stdio.h>

enum { CAP = 8 };

typedef struct {
    int ok;
    int sum;
    int visits;
} SumResult;

int valid_length(int n) {
    return n >= 0 && n <= CAP;
}

/* Caller supplies CAP initialized int slots, each from -9 through 9. */
SumResult prefix_sum(const int a[], int n) {
    SumResult result = {0, 0, 0};
    if (!valid_length(n)) {
        return result;
    }
    result.ok = 1;
    for (int i = 0; i < n; i = i + 1) {
        result.sum = result.sum + a[i];
        result.visits = result.visits + 1;
    }
    return result;
}

int pair_steps(int n) {
    if (!valid_length(n)) {
        return -1;
    }
    int steps = 0;
    for (int i = 0; i < n; i = i + 1) {
        for (int j = i + 1; j < n; j = j + 1) {
            steps = steps + 1;
        }
    }
    return steps;
}

int halving_steps(int n) {
    if (!valid_length(n)) {
        return -1;
    }
    int remaining = n;
    int steps = 0;
    while (remaining > 0) {
        remaining = remaining / 2;
        steps = steps + 1;
    }
    return steps;
}

int main(void) {
    const int values[CAP] = {4, -1, 7, 0, 3, -2, 1, 5};
    int n = 4;
    SumResult result = prefix_sum(values, n);
    if (!result.ok) {
        return 1;
    }
    printf("sum: %d visits: %d\n", result.sum, result.visits);
    printf("pairs: %d halves: %d\n", pair_steps(n), halving_steps(n));
    return 0;
}

ठीक यही आउटपुट है:

sum: 10 visits: 4
pairs: 6 halves: 3

अनुबंध और रिकॉर्ड का ज़रूरी सिंटैक्स

prefix_sum के कॉलर को ठीक CAP आरंभिक मानों वाले int तत्वों का जीवित ऐरे देना है; हर मान -9 से 9 के बीच हो। कॉल के दौरान ऐरे नहीं बदलता। const int a[] C के ऐरे-पैरामीटर नियम से उसी मूल भंडारण को संदर्भित करता है; पूरा ऐरे कॉपी नहीं करता और उसकी capacity नहीं खोजता। NULL, खत्म हो चुका भंडारण और सीमा के बाहर तत्व इस storage/value अनुबंध में नहीं हैं। फ़ंक्शन किसी तत्व को पढ़ने से पहले n की अलग runtime जाँच करता है। n=0 वाले खाली हिस्से में कोई तत्व नहीं पढ़ता, लेकिन वही मौजूद भंडारण फिर भी दिया जाता है।

typedef struct में ok, sum और visits वाला रिकॉर्ड बनता है। SumResult result = {0,0,0} घोषणा के क्रम में आरंभिक मान देता है। फ़ंक्शन रिकॉर्ड का मान लौटाता है; कॉलर result.visits जैसे डॉट से फ़ील्ड चुनता है। ok=1 सफलता है; ok=0 लंबाई अस्वीकार करना है, इसलिए बाकी आरंभिक फ़ील्ड को उत्तर न मानें। pair_steps और halving_steps अमान्य n पर -1 लौटाते हैं; वैध गिनतियाँ गैर-ऋणात्मक हैं, इसलिए विफलता-संकेत उनसे नहीं टकराता।

enum { CAP = 8 }; पूर्णांक स्थिरांक देता है। && तार्किक AND और ! शून्य की जाँच है। for लूप चर आरंभ करता है, शर्त जाँचता है, सही हो तो बॉडी चलाता है और फिर अपडेट करता है। i और j स्थानीय लूप चर हैं। गैर-ऋणात्मक पूर्णांक का / 2 भिन्नांश छोड़ देता है। printf में %d पूर्णांक छापता है और \n नई पंक्ति शुरू करता है। दोनों काउंटर फ़ंक्शन केवल अपने कॉपी हुए n को पढ़ते हैं; एक printf में उनकी कॉल साझा स्थिति नहीं बदलतीं।

वैध n पर prefix केवल 0 से n-1 इंडेक्स पढ़ता है; योग -72 से 72 तक है। pairs अधिकतम 28 घटनाएँ गिनता है। आधा करने में अधिकतम चार iteration हैं और शून्य आता है। i+1 जैसे इंडेक्स अपडेट अधिकतम 8 हैं। ये C के न्यूनतम int दायरे में भी आते हैं। अमान्य -1 या 9 लंबाई कोई लूप शुरू किए बिना विफलता लौटाती है। छोटे int की सुरक्षा का यह प्रमाण असीमित इनपुट पर न लगाएँ।

हल सहित ट्रेस 2: लूप से सटीक गिनती

n=4 पर prefix_sum, 4,-1,7,0 पढ़ता है: चलते योग 4,3,10,10 और visits 1,2,3,4 हैं। शुरुआती तत्व या चलता योग शून्य हो, तब भी ठीक n तत्व देखता है।

pair_steps(4) की बॉडी जोड़ी (0,1), (0,2), (0,3), (1,2), (1,3), (2,3) पर चलती है: छह जोड़ियाँ। बाहरी इंडेक्स से अंदर की 3,2,1,0 iterations मिलती हैं। सामान्य गिनती (n-1)+(n-2)+...+1+0 = n(n-1)/2 है। गुणनफल गणित का सूत्र है; C कोड असीमित गुणनफल निकालने के बजाय सीमित काउंटर बढ़ाता है।

halving_steps(4) में remaining, 4 से 2 से 1 से 0 होता है, इसलिए तीन iterations। n=5 पर 5,2,1,0 आता है, फिर तीन: पूर्णांक भाग छोड़ा हुआ भिन्नांश नहीं बचाता। धनात्मक n की सटीक गिनती floor(log2 n)+1 है। log2 n वह घात x है जिसके लिए 2 की घात x = n; floor का अर्थ नीचे की ओर पूर्णांक लेना है। n=0 में शून्य iterations अलग से लेते हैं, log2 0 नहीं निकालते।

बड़े आकार वाले पैटर्न में prefix visits Θ(n) हैं। Pair executions Θ(n का वर्ग) हैं: n>=2 पर n का वर्ग/4 <= n(n-1)/2 <= n का वर्ग/2 है। n बढ़ने पर आधा करने की iterations Θ(log n) हैं (n>=2 का threshold लें)। लॉग का निश्चित आधार बदलने से केवल स्थिर गुणक बदलता है। ये गिनी घटनाओं की tight सीमाएँ हैं।

पूरे लूप में शर्त-जाँच और इंडेक्स अपडेट भी होते हैं। संबंधित iteration पर स्थिर काम जुड़ता है; बताए मॉडल में बड़े n की समय-श्रेणियाँ नहीं बदलतीं। n=1 पर शून्य pair-बॉडी चलने का अर्थ शून्य कुल समय नहीं: फ़ंक्शन वैधता, आरंभ और लूप-जाँच फिर भी करता है। लौटाया काउंटर अपने-आप पूरा runtime नहीं मापता।

हल सहित ट्रेस 3: सीमा लगाने से पहले स्थिति चुनें

सामान्य linear search मानें, जो 0,1,... इंडेक्स पर बराबरी जाँचकर पहले मैच पर रुकता है। n>=1 के लिए key-equality तुलना गिनें। पहला तत्व मैच करने पर 1 तुलना। केवल आखिरी तत्व मैच करे या कोई मैच न हो, तो n। n=4 में ये उदाहरण 1 बनाम 4 तुलना देते हैं।

दोनों फलनों की ऊपरी और निचली सीमाएँ हैं। Best-case फलन O(1), Ω(1) और ढीली O(n) सीमा भी रखता है। Worst-case फलन O(n), Ω(n), Θ(n) है। इसलिए स्थिति बताए बिना “linear search Ω(n) है” कहना भ्रामक हो सकता है: best-case फलन Ω(n) नहीं, जबकि worst-case फलन है। Worst-case की निचली सीमा अधिकतम लागत के पर्याप्त बड़े होने को बताती है; हर इनपुट पर वही लागत होने को नहीं।

औसत के लिए अनुपस्थित target, मैच-स्थान और उनकी प्रायिकता की मान्यताएँ चाहिए। जैसे target हमेशा ठीक एक बार मौजूद हो और n में हर स्थान समान संभावना वाला हो, तो इस तुलना की औसत (n+1)/2 है। इस औसत के लिए यह पर्याप्त मॉडल है; यही औसत देने वाला अकेला संभावित वितरण नहीं। यह वितरण बिना बताए न मानें। अगले पाठ में खोज के कार्यान्वयन और duplicate नियम आएँगे।

सहायक स्थान, कुल आवंटित भंडारण नहीं

बताएँ कि क्या बाहर रखा है। यहाँ auxiliary space यानी पहले से दिए इनपुट और लौटाए आउटपुट के अलावा काम की जगह है; runtime call stack इसमें शामिल है। इन iterative helpers में निश्चित संख्या के scalar चर और निश्चित आकार का स्थानीय रिकॉर्ड Θ(1) सहायक स्थान लेते हैं। n बार पढ़ने का अर्थ n काम की चीज़ें एक साथ रखना नहीं।

main उदाहरण पहले से आठ input तत्वों की जगह रखता है, चाहे n कुछ भी हो। बड़े आकार वाले रूप में n तत्वों का इनपुट ऐरे Θ(n) input storage लेता है, भले helper की auxiliary space Θ(1) हो। सभी n तत्वों की कॉपी करने वाला अलग ऐरे Θ(n) अतिरिक्त जगह लेगा; उसे “temporary” कहने से वह constant space नहीं बनता। Driver और एल्गोरिदम का space bound अलग हो सकता है।

एक साधारण रिकर्सिव शृंखला में घटती लंबाई पर हर कॉल इंतज़ार करे तो n+1 source-level कॉल एक साथ सक्रिय हो सकती हैं। हर फ़्रेम की जगह स्थिर मानने वाले परंपरागत बिना optimization के call-stack मॉडल में यह Θ(n) सहायक stack space है, भले हर अलग कॉल में कुछ ही scalar हों। यह optimizing compiler में वास्तविक bytes की संख्या का कथन नहीं है। संतुलित रिकर्शन, कुल कॉल और सबसे बड़ी सक्रिय गहराई अलग जाँचें; पिछला frame-count पाठ याद रखें, सभी कॉल को एक-साथ मेमोरी न मानें।

एक सटीक उपमा

निरीक्षण में दरवाज़ा-जाँच की गिनती सोचें। n दरवाज़े एक-एक देखना रैखिक, हर बिना क्रम वाली दरवाज़ा-जोड़ी जाँचना द्विघात और बचे संभावित समूह का लगभग आधा बार-बार छोड़ना logarithmic rounds देता है। एक जाँच का समय अलग मान्यता है। नोटबुक के एक साथ काम में लगे पन्ने सहायक स्थान बताते हैं, कुल जाँचे दरवाज़े नहीं। यह गिनी क्रियाओं और रखे काम की उपमा है, असली CPU समय या हर प्रोग्राम की अपने-आप गारंटी नहीं।

मुख्य बातें

• इनपुट आकार, गिनी क्रिया, स्थिति-नियम और बड़े आकार वाला परिवार स्पष्ट करें।
• O पर्याप्त बड़े आकार की ऊपरी, Ω निचली और Θ दोनों सीमाएँ देता है।
• सीमा सटीक सूत्र होना ज़रूरी नहीं। O ढीली सीमा हो सकती है।
• Best/worst/average इनपुट बताते हैं; Ω/O/Θ के दूसरे नाम नहीं।
• Average-case के लिए probability model चाहिए।
• अंदर-अंदर लूप की असली सीमाएँ गिनें; बार-बार आधा करना और एक-एक घटाना अलग हैं।
• Auxiliary space एक-साथ अतिरिक्त भंडारण गिनती है, बताए मॉडल के सक्रिय कॉल फ़्रेम सहित।
• सुरक्षित सीमित C उदाहरण असीमित इंडेक्स, overflow या stack depth की अनुमति नहीं देते।

पहले स्वयं करें, फिर मिलाएँ

1. f(n)=7n+4 की tight सीमा सिद्ध करें। उत्तर: n>=1 पर 7n <= 7n+4 <= 11n है; c=7, C=11, n0=1 से Θ(n)। O(n का वर्ग) भी सही, लेकिन ढीली सीमा है।
2. pair_steps(3) और halving_steps(3) का ट्रेस करें। उत्तर: जोड़ी (0,1),(0,2),(1,2) से 3; remaining 3,1,0 से 2 आधा करने वाली iterations। फ़ंक्शन अलग घटनाएँ गिनते हैं और उनके लौटाए पूर्णांक CPU समय नहीं बताते।

छह मौलिक अभ्यास प्रश्न

ठीक एक विकल्प चुनें। ये मौलिक शुरुआती अभ्यास हैं, पिछले वर्ष के प्रश्न या पूरे पाठ्यक्रम की परीक्षा नहीं।

1

पूर्णांक n बढ़ने पर f(n)=3n+2 के लिए कौन-सा कथन सही है?

A. यह O(n का वर्ग) है, इसलिए Θ(n का वर्ग) भी है। B. यह Θ(n) है, और O(n का वर्ग) सही लेकिन ढीली ऊपरी सीमा भी है। C. अतिरिक्त +2 के कारण यह O(n) नहीं है। D. 3 और 2 स्थिरांक होने से यह Θ(1) है।

2

बताए गए गैर-ऋणात्मक लागत-फलन f(n) के लिए Ω(g(n)) का सही अर्थ क्या है?

A. यह हमेशा एल्गोरिदम के best-case इनपुट बताता है। B. यह कहता है कि हर इनपुट की लागत ठीक g(n) है। C. यह केवल worst case पर लागू ऊपरी सीमा है। D. यह पर्याप्त बड़े आकार पर g(n) के धनात्मक स्थिर गुणक की निचली सीमा देता है, चाहे कौन-सा इनपुट-स्थिति फलन चुना हो।

3

Linear search पहले मैच पर रुकता है। n>=1 के सभी अनुमत ऐरे/target में key-equality तुलना गिनें, अनुपस्थित target सहित। Best और worst की tight सीमाएँ क्या हैं?

A. Θ(1) और Θ(n) B. Ω(n) और O(1), क्योंकि Ω best और O worst है C. Θ(n) और Θ(n), क्योंकि ऐरे में n तत्व हैं D. Θ(1) और Θ(log n), क्योंकि हर खोज इनपुट आधा करती है

4

ठीक दिखाए सुरक्षित उदाहरणों में pair_steps(5) और halving_steps(5) क्या लौटाते हैं?

A. 25 और 5 B. 15 और 2 C. 10 और 3 D. 10 और 5

5

Iterative helper पहले से दिए input ऐरे के n तत्व पढ़ता है, एक scalar लौटाता है और केवल निश्चित संख्या के scalar working चर रखता है। पाठ के नियम में उसकी auxiliary-space वृद्धि क्या है?

A. Θ(n), क्योंकि n तत्व पढ़ने से n नई कॉपी रखी जाती हैं B. Θ(1), जबकि दिया input storage अलग से Θ(n) हो सकता है C. Θ(n का वर्ग), क्योंकि input और loop index दोनों हैं D. Θ(log n) होना चाहिए क्योंकि लूप चर दोबारा इस्तेमाल करते हैं

6

n>=1 तत्वों में सामान्य first-match linear search की औसत key तुलना (n+1)/2 होने के लिए कौन-सी मान्यता पर्याप्त है?

A. केवल best लागत 1 और worst n पता हों; इनपुट-वितरण न हो B. हर query अनुपस्थित हो C. हर query पहले स्थान पर मिले D. Target ठीक एक बार मौजूद हो और n में हर स्थान समान संभावना वाला हो

समझाए गए उत्तर

1: B

A गलत है: द्विघात ऊपरी सीमा से द्विघात निचली सीमा नहीं मिलती; f(n)/n² शून्य की ओर जाता है।

B सही है: n>=1 पर 3n<=f(n)<=5n और 5n<=5n² है।

C गलत है: n>=1 पर +2 भी स्थिर-गुणक ऊपरी सीमा 5n में समा जाता है।

D गलत है: n बढ़ने पर 3n बिना सीमा बढ़ता है।

2: D

A गलत है: best case लागत-फलन चुनना है; उसकी निचली सीमा अलग सवाल है।

B गलत है: सीमा असमानता है, सटीक सूत्र या सभी इनपुट की बराबरी नहीं।

C गलत है: Ω निचली और O ऊपरी सीमा है; दोनों किसी बताए best या worst फलन पर लग सकते हैं।

D सही है: कोई निश्चित c>0 और n0 ऐसे हों कि हर n>=n0 पर c*g(n)<=f(n) हो।

3: A

A सही है: पहले स्थान पर बराबरी की एक तुलना; अनुपस्थित या केवल आखिरी मैच की n।

B गलत है: सीमा की दिशा और इनपुट-स्थिति मिल गई हैं, तथा असली वृद्धि उलट गई है।

C गलत है: पहले मैच पर रुकने से बाकी n-1 तत्व नहीं देखने पड़ते।

D गलत है: सामान्य linear search एक-एक तत्व बढ़ता है, आधे उम्मीदवार नहीं छोड़ता।

4: C

A गलत है: जोड़ी में i<j चाहिए, सभी 5×5 क्रम वाले स्थान नहीं; आधा करना एक-एक घटाना नहीं।

B गलत है: स्वयं-जोड़ियाँ जोड़ने से 15 मिलता है, लेकिन i<j उन्हें निकालता है; आधा करने में तीन iterations हैं।

C सही है: जोड़ी 4+3+2+1+0=10; remaining 5→2→1→0, तीन कदम।

D गलत है: जोड़ी सही है, लेकिन दो से भाग देने पर तीन iterations में शून्य आता है, पाँच में नहीं।

5: B

A गलत है: क्रम से पढ़ने पर हर तत्व की अलग कॉपी के लिए जगह नहीं बनती।

B सही है: एक साथ काम की जगह स्थिर है; बताए नियम में दिया input और लौटाया output बाहर हैं।

C गलत है: दो प्रकार का भंडारण साथ होने से उनकी माप गुणा नहीं होती।

D गलत है: बढ़ता logarithmic stack या buffer बताया नहीं है; working चरों की संख्या निश्चित है।

6: D

A गलत है: केवल best और worst सिरों से प्रायिकता या औसत तय नहीं होती।

B गलत है: अनुपस्थित target हर बार n तुलना लेता है।

C गलत है: तब हर query एक तुलना लेती है, सामान्यतः (n+1)/2 नहीं।

D सही है: लागत 1 से n तक समान संभावना वाली है, इसलिए (1+2+...+n)/n=(n+1)/2।

अगला कदम और सीमा

आगे यही शब्दावली linear/binary search और insertion/selection sort पर लगाएँ। यह मौलिक बुनियाद पूरे Algorithms को नहीं पढ़ाती और मौजूदा कोर्स का परीक्षा-वर्ष नहीं बदलती। हिंदी व्याख्याएँ सीखने में सहायता हैं।