-1

I am trying to find an algorithm to solve the following equation:

∑ max(ai, x) = y

in which the ai are constants and x is the variable.

I can find an algorithm with O(n log n) time complexity as follows:

First of all, sort the ai in O(n log n) time, and arrange intervals
(−∞, a0), (a0, a1), …, (ai, ai+1), …, (an−1, an), (an, ∞)

Then, for each interval, assume x belongs to this interval, and solve the equation. We could get a , and then test whether belongs to this interval or not. If belongs to the corresponding interval, we will assign to x, and return x. On the other hand, we will try the next interval until we get the solution.

The above method is an O(n log n) algorithm due to the sort. With the definition of the equation-solving problem, I expect an algorithm with O(n) time complexity. Is there any reference for this problem?

7
  • Is there any algorithm to solve equation? As a developer you should define the algorithm
    – B001ᛦ
    Aug 24, 2016 at 8:54
  • Is there any algorithm to solve equation in program language Which program language ? Aug 24, 2016 at 8:57
  • 1
    I'd guess than O(n) is ambitious, since unless the a's are sorted it looks like O(n) just to evaluate the function, and so to solve in O(n) would requre a constant number of evaluations.
    – dmuir
    Aug 24, 2016 at 12:57
  • Assume for the moment that b_i are the coefficients from your input, but in sorted order, so b_i <= b_(i+1). As you essentially already wrote, if b_i <= x <= b_(i+1) then the result is i * x + b_(i+1) + … + b_n. Solving for x you get x = (y - b_(i+1) - … - b_n) / i and putting that back into your inequality you have i * b_i < y - b_(i+1) - … - b_n < i * b_(i+1). Concentrating on one of the inequalities, you want the largest i such that i * b_i < y - b_(i+1) - … - b_n. But in order to make this work on unsorted a_i, you'd need something similar to the median of medians.
    – MvG
    Aug 24, 2016 at 22:10
  • @MvG Why would you need the median? You can calculate the partial sum incrementally in a single linear pass. For any b_i, the calculation of x takes then constant time and you just need to check if it is smaller than the next b_í+1. If not, continue to the next one. Aug 25, 2016 at 12:16

2 Answers 2

1

First of all, this only has a solution if the sum of all a_i is smaller than y. You should check this first, because the algorithm below depends on this property.

Assume that we have chosen some pivot p from all a_i and want to calculate the x that corresponds to the interval [p, q), where q is the next larger a_i. This is:

x calculation

If you move p to the next larger a_i, x changes as follows:

x update

, where p' is the new pivot and n is the old number of a_i that are smaller or equal to p. Under the assumption that the sum of all a_i is smaller than y, this clearly leads to a decrease of x. Similarly, if we choose a smaller p, x is increased.

Coming back to the first equation, we can observe the following: If x is smaller than p, we should choose a smaller p. If x is greater than the smallest of the greater a_is, we should choose a larger p. In every other case, we have found the right x.

This can be utilized in a quick select procedure. @MvG's comment brought me onto this track. All credits for the quick select idea go to him. Here is some pseudo code (modified version from Wikipedia):

findX(list, y)
    left := 0
    right := length(list) - 1
    sumGreater := 0 // the sum of all a_i greater than the current interval
    numSmaller := 0 // the number of all a_i smaller than the current interval
    minGreater := inf //the minimum of all a_i greater than the current interval
    loop
        if left = right
            return (y - sumGreater) / (numSmaller + 1)
         pivotIndex := medianOfMedians(list, left, right)
         //the partition function will also sum the elements larger than the pivot, 
         //count the elements smaller than the pivot, and find the minimum of the
         //larger elements
         (pivotIndex, partialSumGreater, partialNumSmaller, partialMinGreater) 
             := partition(list, left, right, pivotIndex)

         x := (y - sumGreater - partialSumGreater) / (numSmaller + partialNumSmaller + 1)

        if(x >= list[pivotIndex] && x < min(partialMinGreater, minGreater))
            return x
        else if x < list[pivotIndex]
            right := pivotIndex - 1
            minGreater := list[pivotIndex]
            sumGreater += partialSumGreater + list[pivotIndex]
        else
            left := pivotIndex + 1
            numSmaller += partialNumSmaller + 1

The key idea is that the partitioning function gathers some additional statistics. This does not change the time complexity of the partitioning function because it requires O(n) additional operations, leaving a total time complexity of O(n) for the partitioning function. The medianOfMedians function is also linear in time. The remaining operations in the loop are constant time. Assuming that the median of medians yields good pivots, the total time of the entire algorithm is approximately O(n + n/2 + n/4 + n/8 ...) = O(n).

4
  • The “… assuming … good pivots … time … is approximately … O*(*n)” sounds a bit weak. Do you think this has “O*(*n)” in the worst case? If so, what would we need to prove that? If not, what would a worst case input look like? Personally I think this might indeed be O*(*n) in the worst case, since you can guarantee to remove half the elements in each run of the loop. BTW: your loop indentation is confusing. Where does the loop end? Should there be a recursive call somewhere? If not, what are the function arguments used for?
    – MvG
    Aug 25, 2016 at 15:41
  • I think, the worst-case complexity depends on the implementation of median of medians. If the version from Wikipedia is used, we are guaranteed to reduce the list size by at least 30% each step. This is enough to achieve linear time. Good spot on the formatting; was just caused by copy-pasting. Aug 25, 2016 at 15:56
  • I was under the impression that you'd simply call the whole median-of-medians process, which determins the median in O*(*n). As long as it keeps that complexity, it doesn't matter hwo much it reduces at each step. In the end you have obtained the median, which will partition the input into two halves of equal size (±1).
    – MvG
    Aug 25, 2016 at 17:07
  • I've posted my own answer. Mainly motivated by the fear that comments might get deleted one day, but also in order to work out pseudocode following my own lines of thought. I hope I eventually got rid of all the potential off-by-one errors I had while formulating this.
    – MvG
    Aug 30, 2016 at 19:43
0

Since comments might get deleted, I'm turning my own comments into a coherent answer. Contrary to the original question, I'm using indices 1 through n, avoiding the a0 originally used. So this is consistent one-based indexing using inclusive indices.

Assume for the moment that bi are the coefficients from your input, but in sorted order, so bibi+1. As you essentially already wrote, if bixbi+1 then the result is ix + bi+1 + ⋯ + bn since the first i terms will use the x and the other terms will use the bj. Solving for x you get x = (ybi+1 − ⋯ - bn) / i and putting that back into your inequality you have ibiybi+1 − ⋯ − bnibi+1. Concentrating on one of the inequalities, you want the largest i such that

ibiybi+1 − ⋯ − bn       (subsequently called “the inequality”)

But in order to make this work on unsorted ai, you'd need something similar to the median of medians. That is an algorithm which achieves O(n) guaranteed worst-case behavior for the problem of selecting a median, where the typical quickselect would take O(n²) in the worst case although it usually does quite well in practice.

Actually your problem is not that different from quickselect. You can pick a pivot coefficient, and split the remainder into larger and smaller values. Then you evaluate the inequality for the pivot element. If it is satisfied, you recurse into the list of larger elements, otherwise you recurse into the list of smaller elements, until at some point you have two adjacent elements, one which satisfies the inequality and one which does not.

This is O(n²) in the worst case, since you might need O(n) recursive calls, each of them taking O(n) time to process its input. Just like the O(n²) quickselect itself is suboptimal. The median-of-medians shows that that problem can indeed be solved in O(n). So we either need to find a similar solution here, or reformulate this problem here in terms of finding the median, or write some algorithm wich makes use of the median in a reasonable way.

Actually Nico Schertler found a way to achieve that last option: Take the algorithm I outlined above, but choose the pivot element to be the median. That way you can guarantee that each recursive call will process at most half as much input as the previous call. Since the median of medians itself is O(n) this can be done without exceeding the O(n) bound for each recursive call.

So in pseudocode it's like this (using inclusive indices throughout):

# f: Process whole problem with coefficients a_1 through a_n
f(y, a, n) := begin
  if y < (sum of a_i for i from 1 through n):                             #  O(n)
    throw Error "Cannot satisfy equation"  # Or omit check and risk division by zero 
  return g(a, 1, n, y)                                                    #  O(n)
end

# g: Recursively process part of the problem, namely a_l through a_r
# Precondition: we know inequality holds for i = l - 1 and fails for i = r + 1
# a: the array as provided to f; will get modified in place
# l: left index (inclusive)
# r: right index (inclusive)
# y: (original y) - (sum of a_j for j from r + 1 through n)
g(a, l, r, y) := begin              # process a_l through a_r                O(r-l)
  if r < l:                         # inequality holds in r but fails in l   O(1)
    return y / r                    # compute x for the case of i = r        O(1)
  m = median(a, l, r)               # computed using median of medians       O(r-l)
  i = floor((l + r) / 2)            # index of median, with same tie breaks  O(1)
  partition(a, l, r, m)             # so a_l…a_(i-1) ≤ a_i=m ≤ a_(i+1)…a_r   O(r-l)
  rhs = y - (sum of a_j for j from i + 1 to r)                            #  O((r-l)/2)
  if i * a_i ≤ rhs:                 # condition holds, check larger i
    return g(a, i + 1, r, y)        # recurse in right half of list          O((r-l)/2)
  else:                             # condition fails, check smaller i
    return g(a, l, i - 1, rhs - m)  # recurse in left half of list           O((r-l)/2)
end

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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