Question
1.
2.
3.
4.
Answer (Detailed Solution Below)
Option 3 : $O(1 + \alpha)$
Advertisement
Detailed Solution
सही उत्तर $O(1 + \alpha)$ है।
Key Points
Helpful?
prepsnap.in • Part -AQuestion:
In a hash table using separate chaining with load factor α, what is the average-case time complexity of an unsuccessful search? / लोड गुणांक α वाली पृथक् श्रृंखलन (separate chaining) हैश तालिका में असफल खोज की औसत-स्थिति समय जटिलता क्या है?
1.
$O(1)$
2.
$O(\alpha)$
3.
$O(1 + \alpha)$
4.
$O(n)$
Correct Answer: $O(1 + \alpha)$
An unsuccessful search must scan an entire chain, whose expected length is the load factor α, plus constant hashing overhead, giving $\Theta(1 + \alpha)$ on average. / असफल खोज को पूरी श्रृंखला स्कैन करनी होती है, जिसकी अपेक्षित लंबाई लोड गुणांक α है, साथ ही स्थिर हैशिंग ओवरहेड, अतः औसतन $\Theta(1 + \alpha)$।
Downloaded from PrepSnap (prepsnap.in)