Cormen Edition 3 Exercise 8.1 Question 3 (Page No. 194)

0 votes

19 views

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?

cormen
algorithms
sorting
descriptive

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

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

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

← Prev. Next →

Related questions

0 votes

0 answers

Cormen Edition 3 Exercise 8.1 Question 4 (Page No. 194)
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subsequence are all smaller than the elements in the ... of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)

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

cormen
algorithms
sorting
descriptive

0 votes

1 answer

Cormen Edition 3 Exercise 8.1 Question 2 (Page No. 194)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.

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

cormen
algorithms
asymptotic-notations
descriptive

0 votes

1 answer

Cormen Edition 3 Exercise 8.4 Question 1 (Page No. 204)
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i - 0 to n - 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n - 1 8 sort list B[i] with ... ,B[n-1] together in order illustrate the operation of BUCKET-SORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$

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

cormen
algorithms
sorting
bucketsort
descriptive

0 votes

1 answer

Cormen Edition 3 Exercise 8.3 Question 1 (Page No. 199)
RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

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

cormen
algorithms
sorting
radix-sort
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 Blog Comments

@MiNiPanda Congrax mate for this success !
Mostly authentic links, it can be Stackoverflow,...
While raising objections what works as...
It is mentioned "Left for Evaluation" so no...
I think this discussion will keep on going till...

Cormen Edition 3 Exercise 8.1 Question 3 (Page No. 194)

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

Recent Posts

Recent Blog Comments