Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Quicksort is run on two inputs shown below to... Start Learning for Free
Quicksort is run on two inputs shown below to sort in ascending order:
(i) 1 , 2 , 3 .... n .
(ii) n, n - 1, n - 2 , .... 2, 1
Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
  • a)
    C1 < C2
  • b)
    C1 > C2
  • c)
    C= C2
  • d)
    We cannot say anything for arbitrary n
Correct answer is option 'C'. Can you explain this answer?
Verified Answer
Quicksort is run on two inputs shown below to sort in ascending order:...
Both of given cases are Quicksort Worst cases problem, so comparisons are equal.
View all questions of this test
Most Upvoted Answer
Quicksort is run on two inputs shown below to sort in ascending order:...
The number of comparisons made in quicksort can be given by the recurrence relation:

C(n) = n-1 + C(k) + C(n-k-1)

where C(n) is the number of comparisons made for an input of size n, and k is the number of elements smaller than the pivot.

For input (i) of size n, the pivot will always be the largest element in the array. Therefore, k = 0, and the recurrence relation becomes:

C1(n) = n-1 + C1(0) + C1(n-1) = n-1 + C1(n-1)

This is a linear recurrence relation, and its solution is given by:

C1(n) = (n-1) + (n-2) + (n-3) + ... + 1 + C1(1) = (n-1)(n)/2

So, C1(n) = (n^2 - n)/2

For input (ii) of size n, the pivot will always be the smallest element in the array. Therefore, k = n-1, and the recurrence relation becomes:

C2(n) = n-1 + C2(n-1) + C2(0) = n-1 + C2(n-1)

This is also a linear recurrence relation, and its solution is given by:

C2(n) = (n-1) + (n-2) + (n-3) + ... + 1 + C2(1) = (n-1)(n)/2

So, C2(n) = (n^2 - n)/2

Therefore, both C1(n) and C2(n) have the same number of comparisons, which is given by (n^2 - n)/2.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer?
Question Description
Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer?.
Solutions for Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Quicksort is run on two inputs shown below to sort in ascending order:(i) 1 , 2 , 3 .... n .(ii) n, n - 1, n - 2 , .... 2, 1Let C1, and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,a)C1 < C2b)C1 > C2c)C1= C2d)We cannot say anything for arbitrary nCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev