13

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few ...


11

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional. Of course, sorting may be too much work; we only need the biggest two ...


9

If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $...


6

The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$: Compare $a_1$ and $a_2$, $a_3$ and $a_4$, and so on. Store only the smallest of each pair in a list $b_1,\ldots,b_{n/2}$. Repeat $k-1$ more times to get the minimum $a_{\min}$. Let $L$ be the set of all $k$ elements which were compared to $a_{\min}$ and were ...


6

It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. ...


4

Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 ...


4

No, it's not optimal. Do you know an efficient way of finding the smallest number in an array? Knowing the smallest number, could you adapt that method to find the second smallest?


4

This could be a great application and test case for the Souper project. Souper is a superoptimizer -- a tool that takes a short sequence of code as input, and tries to optimize it as much as possible (tries to find an equivalent sequence of code that will be faster). Souper is open source. You might try running Souper on your code snippet to see if it can ...


4

Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is: Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has exactly $\ell$ elements smaller than it (i.e., it is the $(\...


4

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b_{m-1},\ldots,b_{m-k},1$, and use this to find the $(k+1)$th MSB of the median. This algorithm uses $O(\log n)$ passes and $O(\...


4

This is an interesting question. Here is an algorithm. Iterate through the array to obtain $m$ and $M$. If $m=M$, we are done. Otherwise, let $\delta=\frac{M-m}n$. For $i=0,1,\cdots,n+1$, let $L_i$ be an empty list of numbers. Iterate through the array again. For each $a_j$, if $\lfloor (a_j-m)/\delta\rfloor=k$, then append $a_j$ to $L_k$ and $L_{k+1}$. ...


4

The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \leq A[q+1],\ldots,A[r]$. The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A[p],\ldots,A[r]$. To ...


3

Consider the following series $S = n + \lceil n/2 \rceil + \lceil n/4 \rceil + ... + 1$ There are $\lceil \log_2 n \rceil + 1$ terms but the sum is less than $2^{\lceil \log_2 n \rceil+1} < 4n$ always. Similarly, in your algorithm even though you have $\log n$ recursions, each recursion successively does a fraction of work. Hence the total work done in ...


3

Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons. Sort the first two pairs. [ 2 comparisons] Order the pairs w.r.t. their respective larger element. [ 1 comparison] Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$. Now there are 3 elements less than $d$, ...


3

Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$. It is a modified Quicksort algorithm that sorts the array but stops early, leaving the beginning part correct (in this case the first two elements) and the rest of the array in whatever partly-sorted state is most convenient....


3

You can use a $21^3$ table that gets three integers and outputs the largest two. You can then use three table lookups: T[T[T[441*a+21*b+c]*21+d]*21+e] Similarly, using a $21^4$ table, you can reduce it to two table lookups, though it's not clear that this would be faster. If you really want a small table, you can use two $21^2$ tables to "sort" two ...


3

Let $z$ be the median of $A$, and split $A$ into two subarrays $B,C$: the array $B$ consists of all numbers at most $z$ (including $z$), and the array $C$ consists of all number at least $z$ (including $z$). Assuming for simplicity that $n$ is even and that all elements in $A$ are distinct, we can write $$ B = b_0,\ldots,b_{n/2}, \\ C = c_0,\ldots,c_{n/2}, $$...


3

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the ...


2

It depends on the structure of your heap. You can create a heap based around the median being the first element, but in a typical min or max heap, it's going to be O(n). Check this post: https://stackoverflow.com/questions/2579912/how-do-i-find-the-median-of-numbers-in-linear-time-using-heaps


2

Initially assume that k is odd. Algorithm: Find the median of the unsorted array. This can be done using Selection Algorithm in O(n) time. Recursively find the median of the two partition thus obtained. Time complexity: O(nlog(k)) Analysis: In each recursive step, you double the items obtained so far. So the number of steps would be log(k). Also in each ...


2

I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$. Here is a recursive (divide-and-conquer) algorithm: Select the median of the array $A$ and use it to partition the array into $A_l$ and $A_r$ Do the same thing above recursively on $A_l$ and $A_r$. It is easy to see that the depth of the recursive is $O(\lg k)$. Unfolding the recursive tree, you ...


2

Your idea works out. The idea is to maintain a heap of size $k$ which contains exactly one element from each array. For each array $A_i$, we maintain an index $p_i$ which keeps track of the position of the current element in the array. Initially, $p_i = n_i$, and we insert $A_i[n_i]$ into the heap. We then repeat the following $m$ times: Extract the maximum ...


2

Step 1. Use QuickSelect to find the $k$th largest number in the array. Call it $x$. Step 2. Use QuickSelect to find the $k+c$th largest number in the array. Call it $y$. Step 3. Find all elements in the array that are at least $x$ and at most $y$. This can be done by simply iterating over the array and comparing each element to $x$ and $y$. Each step ...


2

If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which ...


2

If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather non-obvious transformation into maximum flow. The algorithm is described in the Wikipedia page linked above. Briefly, it involves setting the capacity of each ...


2

Proceed in two phases. Determine the median of the input. Partition the input with the median as the pivot (cf. Quicksort). Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.


2

Consider another min-priority queue $q$. The result will be in array $a$. Push the top of the heap into $q$. For $i$ from $1$ to $\log n$: Set $a_i = \text{pop}(q)$. Push the two sons of $a_i$ in the heap into $q$. $q$ may be implemented with a min-heap of size $O(\log n)$, so the overall complexity is $O(\log n \log \log n)$.


2

You can implement FINDLARGEST recursively: FINDLARGEST(k, vertex) # call with vertex = root if value(vertex) < k: exit the function output vertex FINDLARGEST(k, left-child(vertex)) FINDLARGEST(k, right-child(vertex)) If there are $m$ vertices whose value is at least $k$, then FINDLARGEST explores at most $3m$ vertices: each eligible vertex ...


2

You can use the inequality $\log (1+x) < x$ (valid for $x > 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows: $$ \log \left(\frac{n'}{3} + 1\right) = \log \left(\frac{n'}{3} \cdot \left(1 + \frac{3}{n'}\right)\right) = \log \frac{n'}{3} + \log \left(1 + \frac{3}{n'}\right) < \log \frac{n'}{3} + \...


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