1
$\begingroup$

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!

$\endgroup$
8
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – rentbuyer
    Oct 9 '20 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.