All Courses
Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity Get the App Login Join for Free
Sign in Open App
Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  What is recurrence for worst case of QuickSor... Start Learning for Free
SaveJoin the Discussion on the App
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 Test
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) void exchange(int *a, int *b) { 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; for (j = si; j <= ei - 1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); 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); } } [/sourcecode]
View all questions of this test
< Previous Question Next Question >
Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Top Courses for Computer Science Engineering (CSE)View all

Top Courses for Computer Science Engineering (CSE)

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?.
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

Top Courses for Computer Science Engineering (CSE)

Explore Courses

Suggested Free Tests

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
Get App
© 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