What is the time complexity of the Quicksort algorithm?
What is the time complexity of the Quicksort algorithm?
क्विकसाॅर्ट एल्गोरिथ्म की टाइम काॅम्प्लेक्सिटी क्या है?
Detailed Solution & Logic
O(n log [No])
Explanation / व्याख्या :
-
Quicksort is a divide-and-conquer sorting algorithm. In the average and best cases, it divides the array into two parts and sorts them recursively, which gives it a time complexity of O(n log n).
Quicksort एक डिवाइड-एंड-कॉन्कर सॉर्टिंग एल्गोरिथ्म है। औसत और सर्वश्रेष्ठ मामलों में, यह ऐरे को दो भागों में बाँटता है और उन्हें पुनरावर्ती तरीके से सॉर्ट करता है, जिससे इसका टाइम कॉम्प्लेक्सिटी O(n log n) होता है। -
In the worst case, when the pivot is always the smallest or largest element, the time complexity becomes O(n²).
सबसे खराब स्थिति में, जब पिवट हमेशा सबसे छोटा या सबसे बड़ा तत्व होता है, टाइम कॉम्प्लेक्सिटी O(n²) हो जाती है। -
Other options are incorrect:
-
O(n²) → Only occurs in the worst-case scenario.
O(n²) → केवल सबसे खराब स्थिति में। -
O(n) → Incorrect; Quicksort cannot sort in linear time for arbitrary inputs.
O(n) → गलत; Quicksort किसी भी इनपुट के लिए रैखिक समय में नहीं सॉर्ट कर सकता। -
O(log n) → Incorrect; logarithmic time is not sufficient to sort all elements.
O(log n) → गलत; लॉगरिदमिक समय सभी तत्वों को सॉर्ट करने के लिए पर्याप्त नहीं है।
-
Extra Facts / अतिरिक्त तथ्य:
-
Quicksort is in-place, meaning it doesn’t require additional arrays for sorting.
Quicksort इन-प्लेस है, यानी सॉर्टिंग के लिए अतिरिक्त ऐरे की जरूरत नहीं होती। -
It is generally faster in practice than other O(n log n) algorithms like Merge Sort due to low constant factors.
Merge Sort जैसे अन्य O(n log n) एल्गोरिथ्म की तुलना में यह अमल में तेज़ होता है, क्योंकि इसके कॉन्स्टेंट फैक्टर्स कम होते हैं। -
The choice of pivot element (first, last, random, or median) greatly affects the performance.
पिवट एलिमेंट (पहला, आखिरी, रैंडम या मीडियन) का चयन प्रदर्शन को काफी प्रभावित करता है।
Similar Practice Questions
Which of the following is not a search engine?
Which of the following is not a search engine? निम्न में से कौन-सा सर्च इंजन...
Which protocol is used to retrieve emails from a server?
Which protocol is used to retrieve emails from a server? सर्वर से ईमेल प्राप्त करने...
What is the purpose of HTTP in internet communication?
What is the purpose of HTTP in internet communication? इंटरनेट संचार में HTTP का उद्देश्य...
What is the standard extension for downloaded web pages?
What is the standard extension for downloaded web pages? डाउनलोड किए गए वेब पेजों के...
To connect a computer to the Internet, service has to be taken from………….
To connect a computer to the Internet, service has to be taken from…………. किसी कम्प्यूटर...
Which keyboard shortcut is commonly used to print a web page?
Which keyboard shortcut is commonly used to print a web page? वेब पेज को प्रिंट...
What happens when an email in the Outbox is successfully sent?
What happens when an email in the Outbox is successfully sent? जब आउटबाॅक्स (Outbox) का...