Which of the following recurrence relation is related to worst case time complexity of quick sort ?
निम्न में से कौन-सा रिकरेंस रिलेशन क्विक सॉर्ट एल्गोरिथ्म की वर्स्ट केस टाइम कॉम्प्लेक्सिटी से संबंधित है ?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. T(n) = T(n−1) + Cn
Explanation
In the worst case the pivot splits n elements into 0 and n − 1, so T(n) = T(n − 1) + cn = O(n²).
वर्स्ट केस में पिवट n तत्वों को 0 और n − 1 में बाँटता है, अतः T(n) = T(n − 1) + cn = O(n²)।
More Data Structures questions
- A queue follows ……….. .
- Process of inserting an element in stack is called :
- If the elements 'A', 'B', 'C' and 'D' are placed in a queue and are deleted one at a time, in what order will these elements be removed ?
- In a stack, if a user tries to remove an element from an empty stack, it is called :
- A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear), is…
- In directed graph G(V, E) where V = {P, Q, R, S, T} and E = {PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS}, the vertex with maximum in- degree is…