Tag Info

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 ...

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