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

61 views

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

cormen
algorithms
quicksort
time-complexity
descriptive

asked Jun 28 in Algorithms by akash.dinkar12 Boss (41.9k points) | 61 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 by Asim Siddiqui 4 Active (1.3k points)

Please log in or register to add a comment.

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

← Prev. Next →

Related questions

0 votes

1 answer

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 in Algorithms by akash.dinkar12 Boss (41.9k points) | 29 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 in Algorithms by akash.dinkar12 Boss (41.9k points) | 16 views

cormen
algorithms
quicksort
descriptive

0 votes

0 answers

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 in Algorithms by akash.dinkar12 Boss (41.9k points) | 19 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 in Algorithms by akash.dinkar12 Boss (41.9k points) | 46 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

Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam

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

Follow @csegate

Recent Blog Comments

It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...

Lightbox

50,647 questions

56,467 answers

195,381 comments

100,317 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