Bissoy.com
Doctors Medicines MCQs Q&A

What is the worst-case time complexity of the Quick Sort algorithm to sort a list of ‘n’ values?

What is the worst-case time complexity of the Quick Sort algorithm to sort a list of ‘n’ values? Correct Answer O(n<sup>2</sup>)

Concept:

Quicksort is an efficient sorting algorithm. It is also called partition-exchange sort which follows divide and conquer technique

Explanation

In quick sort worst case, the first or the last element is selected at the pivot element.

[ alt="F2 R.S Madhu 17.12.19 D1" src="//storage.googleapis.com/tb-img/production/19/12/F2_R.S_Madhu_17.12.19_D1.png" style="width: 285px; height: 275px;">

For a quicksort, in worst case recurrence relation will become T(n) = T(n-1) + T (1) + n

Recurrence relation gives: T(n) = O (n2). Hence option 2 is correct

Therefore, worst-case time complexity of the Quicksort is O (n2)

Related Questions

Let Xij =I { zi is compared to zj in quick sort algorithm} is an indicator variable, and zi is the ith smallest number. Which of the following sequence of the numbers give the X2,5 = 1? Note: Assume that there is a divide and conquer quick sort algorithm and in partition algorithm the first element of the lists is taken as pivot-element.
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Which of the following assertions are CORRECT? P: Adding 7 to each entry in a list adds 7 to the mean of the list Q: Adding 7 to each entry in a list adds 7 to the standard deviation of the list R: Doubling each entry in a list doubles the mean of the list S: Doubling each entry in a list leaves the standard deviation of the list unchanged
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
Which country did not contribute to the list of the cyclone names?
Randomized quick sort is an extension of quicksort where the pivot is chosen randomly. what is the worst case complexity of sorting a numbers using randomized quick sort?
Match List I with List II List I List II (A) Greedy Best-First Search (I) Space complexity is O(d) where d = depth of the deepest optimal solution (B) A* (II) Incomplete even if the search space is finite. (C) Recursive Best-First Search (III) Optimal if optimal solution is reachable: otherwise, returns the best reachable optimal solution. (D) SMA* (IV) Computation and space complexity is too high.   Choose the correct answer from the options given below:
Match the items of List - II with the items of List - I and select the code of correct matching List - I List - II (a) Chi-square Test (i) Testing the significance of the differences of the mean values among more than two sample groups. (b) ANOVA (F-test) (ii) Testing the goodness of fit of a distribution (c) Z - test (iii) Testing the significance of the difference of the mean values between two large sized samples (d) t - test (iv) Testing the significance of the difference of the mean values between two small sized samples when population standard deviation is not available  
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
For the next cyclone if it is the turn of an Indian name to be chosen, then what will be that name?
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
Which of the following names is a type of a precious stone?
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
Names of which type of cyclones do people remember?