Finding maximum of $n$ many $m$-bit integers

Question

Suppose you want to determine the largest number in an $n$-element set $X = (x_1, x_2, \dots , x_{n})$, where each element $x_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that solves this problem in $O(n + m)$ steps, where at each step, your algorithm compares one of the elements $x_i$ with a constant. In particular, your algorithm must never actually compare two elements of $X$!

My thoughts: I thought about making intervals $[1,2), [2,4), [4,8), \dots , [2^{m-1}, 2^m)$ and somehow associate comparisons with these ranges. But, all of them were in vain. Would be welcome to hear your ideas on solving this!

Answer 1

Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass "peer-review". Consider following algorithm for a RAM machine (// denotes integer division):

algorithm ArrayMax
Input: array $A$ of size $n$; $A[i] \in [1,2^m-1]$
Output: $max(A)$

left  <- 1
right <- 1
max   <- A[0]
while right <= A[0]: right <- 2*right
left <- right // 2
for i = 1...n-1:
    if A[i] <= left: 
        continue
    if A[i] >= right:
        max <- A[i]
        while right <= A[i]: right <- 2*right
        left <- right//2
        continue
    while left-right > 1:
        mid <- (left+right)//2
        if max < mid:
            right <- mid
        else:
            left <- mid
        if A[i] < left:
            break
        else if A[i] >= right:
            max <- A[i]
            delta <- right-left
            left  <- right
            right <- left+delta
            break
return max

The algorithm operates by keeping $left \leq max < right$ and uses the bounds to make comparisons. Notice that if the bounds of $max$ aren't sufficient they are extended via binary search. How can one proof that this algorithm runs in $O(n+m)$? (This is not a rigorous proof; more an idea; if you have improvements please edit or write a comment)

I'll try to outline a proof using a potential function $\Phi(S_i)$ ($S_i$ is the state of the algorithm at iteration $i$). The Potential Method is usually used for data structures. We define: $$\Phi(S_i) = \log2(left-right) \geq 0$$ There are two things that can happen between $S_i$ and $S_{i+1}$ (We only consider the worst case so we'll ignore the first "if" in the loop and focus on the second "if" and the while loop). If the second "if" is triggered the following change occurs in the potential function: $$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx \log2(A[i]))$$ Also the cost of the operation is $T_i \approx \log2(A[i]) - \log2(right) \leq \log2(A[i]) - \log2(max)$ In the second case a binary search occurs which goes to depth $k$ (does $k$ bisections). $$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx j-k$$ Notice that the cost of bisecting is roughly $4*k$ comparisons. Thus the cost including the Potential Function is: $$T_i = O(1) + 4k + 4(\Phi(S_{i+1})-\Phi(S_i)) = O(1) + 4k - 4k = O(1)$$ So basically the second case is for free. Lets now focus one the first case only. Consider that it happens $h$ times in a row. It is easy to see that for the second case to not occur $A[i+1] \geq 2A[i]$ Meaning we can approximate the cumulative cost with: $$\sum_{i=1}^h \log2(2^{i+1}) - \log2(2^i) + (\Phi(S_{i+1})-\Phi(S_i)) = \sum_{i=1}^h 2(\log2(2^{i+1}) - \log2(2^i)) = \sum_{i=1}^h2(i+1-i) = 2h$$ Notice that since the the numbers are limited by $2^m$ we have $h \leq m$. Thus we obtain $O(m + n)$, where $m$ is accounting for the first cases and n is accounting for the second cases. Also the first while loop finding bounds for $A[0]$ runs at most $m$ times. I hope you get my idea, despite the fuzzy argument.