The Gateway to Computer Science Excellence

For all GATE CSE Questions

- Facebook Login
- or
- - Email or Username
  - Password
  - Remember
  - Register | I forgot my password

Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams

Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)

0 votes

73 views

Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.

cormen
algorithms
quicksort
time-complexity
descriptive

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 73 views

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

+1 vote

proof

answered Jul 15, 2019 by Asim Siddiqui 4 Active (1.5k points)

Please log in or register to add a comment.

← Prev. Qn. in Sub. Next Qn. in Sub. →

← Prev. Next →

Related questions

0 votes

2 answers

1

Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 37 views

cormen
algorithms
quicksort
time-complexity
descriptive

0 votes

1 answer

2

Cormen Edition 3 Exercise 7.4 Question 3 (Page No. 184)
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 16 views

cormen
algorithms
quicksort
descriptive

0 votes

1 answer

3

Cormen Edition 3 Exercise 7.2 Question 3 (Page No. 178)
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.

asked Jun 27, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 26 views

cormen
algorithms
quicksort
time-complexity
descriptive

+1 vote

1 answer

4

Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?

asked Jun 27, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 58 views

cormen
algorithms
quicksort
time-complexity
descriptive

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

ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020

All categories
General Aptitude 1.9k
Engineering Mathematics 7.5k
Digital Logic 2.9k
Programming and DS 4.9k
Algorithms 4.4k
Theory of Computation 6.2k
Compiler Design 2.1k
Operating System 4.5k
Databases 4.1k
CO and Architecture 3.4k
Computer Networks 4.2k
Non GATE 1.4k
Others 1.4k
Admissions 595
Exam Queries 573
Tier 1 Placement Questions 23
Job Queries 72
Projects 18

Follow @csegate

Recent Blog Comments

While raising objections what works as...
It is mentioned "Left for Evaluation" so no...
I think this discussion will keep on going till...
do we have to include marks of qs that are left...
@roh6jmon yes, it is there.

Lightbox

50,737 questions

57,317 answers

198,368 comments

105,105 users

Send feedback
My Marks
College Prediction
Useful Links
FAQ
Corrections
Discuss
Copyright
Request
Testimonials
Chat Logs
Chat
Badges
Search tips
Exam Category
Blog Category
Blog Tags
Privacy

Donut Theme with by Amiya Sahu

Powered by Question2Answer

GATE Overflow