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

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!

• I don't see a lower bound anywhere. Oct 6 '20 at 14:12
• This question needs to be a lot more specific about the model of computation used.
– orlp
Oct 6 '20 at 15:12
• In particular, do you allow randomized algorithms? Oct 6 '20 at 15:13
• You appear to have copy-pasted the problem statement from an external source. Plagiarism is not cool. Always credit all copied material. The original source appears to be Jeff Erickson's notes on Lower Bounds, Exercise 4. You didn't copy the hint, though.
– D.W.
Oct 6 '20 at 19:09
• – D.W.
Oct 6 '20 at 19:10

## 1 Answer

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.

• You really boosted me in this forum. There were some people who treated me unfairly, deliberately downvoted me here. However, when it comes to this problem, your answer is very supportive in my point of view. Thank you very much for such a detailed solution! Oct 9 '20 at 21:47