Hot answers tagged

4

In the first exercise you have to merge a constant number of subarrays, i.e., $3$. In the second exercise you'd have to merge $\Theta(n)$ subarrays, each of constant size. If you were able to produce a sorted version of the union of these subarray in time $O(n)$ using a comparison-based algorithm then you'd also have a comparison-based algorithm for the ...


3

Suppose the input size is $n$. The lower bound of any algorithm (such as comparison based or non-comparison based) that solve the Sorting problem is $$\Omega(n)$$ because we need read the input at least once.


2

Question A ِYes just merge them in $\mathcal{O}(n)$. Question B Your problem reduced to merge $k$ sorted lists with $n$ elements, that can be done that in your problem can be done in $\mathcal{O}(n\log n)$. Note that we can't do better than $\Omega(n\log n)$ because according to decision tree, number of leaves: $$\frac{n!}{(10!)^n}$$ So the height of the ...


2

In the pseudocode "use brute force" means "compute the median of the input sequence (with any algorithm) and return it (to the caller)". Eventually all the children calls in the recursion tree starting at the red call to "MomSelect" will terminate and the control will return to the current execution of the algorithm, that will ...


2

Comparison based sorting algorithms require $\Omega(n \log n)$ comparison (notice the big omega). Heapsort uses $O(n \log n)$ comparisons. This is not a contradiction since $\Omega(n \log n) \cap O(n \log n) \neq \emptyset$, i.e., there are functions of $n$ that are both in $\Omega(n \log n)$ and in $O(n \log n)$. To be more precise, all comparison-based ...


2

Let $n$ and $m$+1 be the number of rows and columns, respectively (so that there are $m$ bins). Your problem can solved in $O(nm + m^2)$ time. This is asymptotically optimal unless $m = \Omega(n)$, i.e., you have asymptotically more bins than rows. Maintain the following: A collection of lists $L_1, \dots, L_m$ where $L_j$ stores all rows contained in the $...


2

Your problem is solved in Kahn and Kim, Entropy and sorting.


1

I think I've thought up a solution. First, do a first pass with any decent sorting algorithm you want (like quicksort), which should, at worst, result in only one item that's significantly far from where it should be. Then, choose a width h that's at least 5. for i from 0 to n-h, we look at the group of h items at i, i+1, ..., i+h-1. We make all h*(h-1)/2 ...


1

It's possible to sort your array in linear time by using a method that use comparison based and non-comparison based sorting algorithms as subroutines. First, do a linear scan to find all integer number in range $[\sqrt{n},n\sqrt{n}]$ and put those elements into array $A'$, and put $\sqrt{n}$ remaining elements into an array $A^{''}$. The running time of ...


Only top voted, non community-wiki answers of a minimum length are eligible