Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
quick sort time complexity
akankshay
asked
in
Algorithms
Mar 9, 2016
15,763
views
4
votes
4
votes
the worst case time complexity of quicksort for an elements when the median is selected as the pivot
a. o(n^2)
b.o(n)
c.o(nlogn)
d.o(logn)
algorithms
time-complexity
quick-sort
akankshay
asked
in
Algorithms
Mar 9, 2016
by
akankshay
15.8k
views
answer
comment
Follow
share this
share
0 Comments
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
4
votes
4
votes
Best answer
Answer C) O(nlogn), when median selected as pivot, partition method will divide array into equal halves.. so logn level recursion tree will form with cn work(partition method) at each level..
The recurence would be..
T(n) = 2T(n/2) + Θ(n)
Therefore total time complexity =Θ(nlogn) in all cases
Note:O(n) time algo available for median finding
https://en.m.wikipedia.org/wiki/Median_of_medians
Anurag_s
answered
Mar 9, 2016
edited
Mar 9, 2016
by
abhilashpanicker29
by
Anurag_s
comment
Follow
share this
4 Comments
Show 6 previous comments
by
rajatmyname
commented
Mar 14, 2018
reply
Follow
share this
same recurrence relation will be applied here also
0
0
by
sushmita
commented
Sep 23, 2018
reply
Follow
share this
if all elements are same then worst case partitioning will occur. How O(nlogn) then?
0
0
by
rajatmyname
commented
Sep 24, 2018
reply
Follow
share this
Here it doesn't matter all the elements are same or not because it will divide the array in two equal parts which gives the recurrence relation for best case of quick sort
0
0
Please
log in
or
register
to add a comment.
← Previous
Next →
← Previous in category
Next in category →
Related questions
4
votes
4
votes
3
answers
1
Swati verma
asked
in
Algorithms
Jun 21, 2017
7,609
views
Time complexity of quick sort when we take pivot as the middle element
Time complexity of quick sort when we take pivot from the middle element
Swati verma
asked
in
Algorithms
Jun 21, 2017
by
Swati verma
7.6k
views
algorithms
time-complexity
quick-sort
3
votes
3
votes
2
answers
2
garvit_vijai
asked
in
Algorithms
Jul 1, 2018
3,425
views
Quick Sort Time Complexity
Quick sort gives O(nlogn) worst case performance if the pivot is selected as: a) First element of the array b) Median of first, last and middle elements c) Arithmetic mean of the elements d) None of these Now, the answer is given as Option (b). But, ... order of elements and not on pivot element. So, answer should be option (d) i.e None of these Correct me if I am wrong
garvit_vijai
asked
in
Algorithms
Jul 1, 2018
by
garvit_vijai
3.4k
views
quick-sort
sorting
time-complexity
0
votes
0
votes
1
answer
3
garvit_vijai
asked
in
Algorithms
Nov 16, 2018
903
views
Self Doubt - Quick Sort
Consider the following inputs: 1) 2 2 2 2 2 2 2 2) 1 2 3 4 5 6 7 3) 7 6 5 4 3 2 1 In all three cases, the worst-case time complexity of quicksort is O(n2) My doubt is if I am taking the middle element as a pivot, ... ), right? Can someone explain how we are saying worst-case time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?
garvit_vijai
asked
in
Algorithms
Nov 16, 2018
by
garvit_vijai
903
views
algorithms
quick-sort
time-complexity
0
votes
0
votes
1
answer
4
Purvi Agrawal
asked
in
Algorithms
Oct 13, 2018
3,745
views
Quick Sort
In Quicksort let n/7 th smallest element is chosen using an O(n2 ) algorithm as the pivot. Calculate the worst case time complexity of the algorithm.
Purvi Agrawal
asked
in
Algorithms
Oct 13, 2018
by
Purvi Agrawal
3.7k
views
quick-sort
algorithms
time-complexity
recurrence-relation
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...
Twitter
WhatsApp
Facebook
Reddit
LinkedIn
Email
Link Copied!
Copy