Finding maximum of $n$ many $m$-bit integers
Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass &quot;peer-review&quot;. 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  &lt;- 1
right &lt;- 1
max   &lt;- A[0]
while right &lt;= A[0]: right &lt;- 2*right
left &lt;- right // 2
for i = 1...n-1:
    if A[i] &lt;= left: 
        continue
    if A[i] &gt;= right:
        max &lt;- A[i]
        while right &lt;= A[i]: right &lt;- 2*right
        left &lt;- right//2
        continue
    while left-right &gt; 1:
        mid &lt;- (left+right)//2
        if max &lt; mid:
            right &lt;- mid
        else:
            left &lt;- mid
        if A[i] &lt; left:
            break
        else if A[i] &gt;= right:
            max &lt;- A[i]
            delta &lt;- right-left
            left  &lt;- right
            right &lt;- left+delta
            break
return max

The algorithm operates by keeping $left \leq max &lt; 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 &quot;if&quot; in the loop and focus on the second &quot;if&quot; and the while loop).
If the second &quot;if&quot; 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.