CLRS

CLRS copied to clipboard

It seems that keeping track of all elements which lost to the best requires O(n) space or extra O(n) comparisons. It is interesting that the same time complexity can be...

rualark

This approach of reverse prefix sort will require too many buckets (kn, where k is number of unique symbols) if there is only one string of length n. Alternative solution:...

rualark

A. What are the "rest leaves", that are "labeled 0"?

rualark

Probably a mistake in solution: there cannot be more piles (nk) than number of cards (n). Probably correct answer is Theta(kd)? Also, this solution needs more detailed explanation.

rualark

Solution is correct, but needs more detailed explanation

rualark

Bad phrasing: "Insertion sort was chosen, because it operates well on linked lists". Better: "Insertion sort was chosen, because it has optimal time and requires only constant extra space for...

rualark

b. Reasoning seems wrong. i can be greater or equal to j, for example when there are two adjacent elements, first being less than x and second being greater than...

rualark

The right side of equation right should be $$\frac{n!}{(n-k)!n^k}$$.

ywxktc

the recurrence of this exercise in CLRS 3rd edition is T(n) = 4T(n/2)+n, then the question is without any wrong now.

Kirizen

Probably just a typo: replace i with k in formula

rualark