Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > What is recurrence for worst case of QuickSor...
Start Learning for Free
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
- a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
- b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
- c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
- d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
Correct answer is option 'B'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
What is recurrence for worst case of QuickSort and what is the time co...
The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n-1). So recurrence is T(n) = T(n-1) + T(0) + O(n) The above expression can be rewritten as T(n) = T(n-1) + O(n) 1
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;
{
int x = arr[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}
return (i + 1);
}
/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
Most Upvoted Answer
What is recurrence for worst case of QuickSort and what is the time co...
Recurrence for worst case of QuickSort:
The recurrence relation for the worst case of QuickSort can be defined as:
T(n) = T(n-1) + O(n)
Explanation:
In the worst case scenario, QuickSort chooses a pivot element that is either the smallest or largest element in the array. This leads to an unbalanced partitioning of the array, where one partition contains n-1 elements and the other partition is empty.
Recurrence relation breakdown:
Let's break down the recurrence relation to understand it better:
T(n) = T(n-1) + O(n)
- T(n-1): This term represents the time taken to sort the partition with n-1 elements. Since the pivot element is either the smallest or largest, the partition size reduces by 1.
- O(n): This term represents the time taken to partition the array into two subarrays. In the worst case, the partitioning takes linear time as it needs to compare each element with the pivot.
Time complexity in worst case:
To determine the time complexity, we need to solve the recurrence relation. Let's expand it:
T(n) = T(n-1) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
= ...
= T(1) + O(2) + O(3) + ... + O(n-1) + O(n)
Since each term O(i) is linear in i, we can write it as O(n). Therefore, the recurrence relation can be simplified as:
T(n) = T(1) + O(n) + O(n) + ... + O(n)
= T(1) + O(n^2)
Hence, the time complexity in the worst case of QuickSort is O(n^2).
The recurrence relation for the worst case of QuickSort can be defined as:
T(n) = T(n-1) + O(n)
Explanation:
In the worst case scenario, QuickSort chooses a pivot element that is either the smallest or largest element in the array. This leads to an unbalanced partitioning of the array, where one partition contains n-1 elements and the other partition is empty.
Recurrence relation breakdown:
Let's break down the recurrence relation to understand it better:
T(n) = T(n-1) + O(n)
- T(n-1): This term represents the time taken to sort the partition with n-1 elements. Since the pivot element is either the smallest or largest, the partition size reduces by 1.
- O(n): This term represents the time taken to partition the array into two subarrays. In the worst case, the partitioning takes linear time as it needs to compare each element with the pivot.
Time complexity in worst case:
To determine the time complexity, we need to solve the recurrence relation. Let's expand it:
T(n) = T(n-1) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
= ...
= T(1) + O(2) + O(3) + ... + O(n-1) + O(n)
Since each term O(i) is linear in i, we can write it as O(n). Therefore, the recurrence relation can be simplified as:
T(n) = T(1) + O(n) + O(n) + ... + O(n)
= T(1) + O(n^2)
Hence, the time complexity in the worst case of QuickSort is O(n^2).
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer?
Question Description
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. 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 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. 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 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer?.
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. 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 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. 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 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer?.
Solutions for What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. 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 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer?, a detailed solution for What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer? has been provided alongside types of What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup