BRICS RS-96-42 Brodal & Skyum: Computing k-ary Compositions

BRICS

Basic Research in Computer Science

The Complexity of Computing the k-ary Composition of a Binary Associative Operator

Gerth St�lting Brodal Sven Skyum

BRICS Report Series RS-96-42 ISSN 0909-0878 November 1996 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through World Wide Web and anonymous FTP:

http://www.brics.dk/
ftp://ftp.brics.dk/pub/BRICS

This document in subdirectory RS/96/42/

The Complexity of Computing the k-ary Composition of a Binary Associative

Operator^{∗}

Gerth Stølting Brodal^{†} and Sven Skyum

BRICS^{‡}

Department of Computer Science, University of Aarhus Ny Munkegade, DK-8000 Århus C, Denmark

          {gerth,sskyum}@brics.dk

November 27, 1996

Abstract

We show that the problem of computing all contiguous k-ary compositions of a sequence of n values under an associative and commutative operator requires 3\frac{k−1}{k+1}n − O(k) operations.

For the operator max we show in contrast that in the decision tree model the complexity is (1 + Θ(1/\sqrt{k})) n − O(k). Finally we show that the complexity of the corresponding on-line problem for the operator max is (2 − \frac{1}{k−1}) n − O(k).

∗This work was partially supported by the ESPRIT Long Term Research Program of the EU under contract #20244 (ALCOM-IT).

†Supported by the Danish Natural Science Research Council (Grant No. 9400044).

‡Basic Research in Computer Science, Centre of the Danish National Research Foundation.

Introduction

Given a sequence of values (x_{1}, x_{2}, …, x_{n}) from a universe U and an associative binary operator ⊕, we consider the problem of computing all k-ary compositions of contiguous subsequences of length k. More formally, the problem of computing x_{i} ⊕ x_{i+1} ⊕ ⋯ ⊕ x_{i+k−1} for i = 1, 2, …, n − k + 1. Cooper and Kitchen presented a solution to the problem in [3], which requires 3\frac{k−1}{k+1}n ⊕-operations. We show in Section 1 that this is optimal even if ⊕ is commutative as well. The solution has applications to e.g. the computer vision task of region dilation where a run-length encoding of a region can be grown vertically by or-ring together k-tuples of rows of the region (see [3]). For special operators the k-ary composition problem is simple cases of general problems. For instance, if the universe is the booleans and the operator is disjunction, the general problem is the boolean sum problem [1, 7, 8]. This is the problem of computing n outputs from n inputs where each output is a disjunction of a subset of the inputs. For the general problem the number of operations might be Ω(n^{2}/log n) [8]. In Section 2 we examine how many comparisons are required to solve the problem for the operator max in the decision tree model. We show that the complexity is (1 + Θ(1/\sqrt{k})) n − O(k). The problem is a special case of the set-maxima problem [2, 4] where the problem is to compute maxima for n arbitrary subsets of the input. It is open whether subsets exist such that the complexity of the problem is Ω(n log n). Efficient solutions to other special cases than the one dealt with in this paper have been given. In [2] an O(n) algorithm is given for the case where the sets are the hyperplanes in a projective geometry. For the general set-maxima problem an optimal (within a constant factor) randomised algorithm with expected complexity O(n) was presented in [4]. Finally, the corresponding on-line problem of computing maxima is considered in Section 3. For the on-line problem it is required that the set maxima are computed from left to right. That is, all maxima of k consecutive elements in {x_{1}, x_{2}, …, x_{i−1}} are computed before reading x_{i}. We show that the on-line complexity is (2 − \frac{1}{k−1}) n − O(k).

1 The general problem

In this section we consider how many ⊕-operations are required to compute the k-ary compositions. An upper bound was given in [3]. We prove that the bound achieved in [3] is optimal even if ⊕ is commutative as well as associative. Let ⊕ be commutative as well as associative and let (x_{1}, x_{2}, …, x_{n}) be a sequence of n values from a universe U. For a subset M ⊆ {1, 2, …, n}, let S_{M} be the composition ⨁_{i∈M} x_{i}. The problem is to compute

S_{{1,2,...,k}}, S_{{2,3,...,k+1}}, …, S_{{n−k+1,n−k+2,...,n}}.

We denote the number of ⊕-operations required by A(n, k). We need the following notion of a computation graph and a combinatorial lemma about them.

Definition 1.1 A directed acyclic graph G = (V, E) is a computation graph if V consists of three kinds of nodes: input, computation and output nodes. Input nodes have indegree 0 while computation and output nodes have indegree 2. Output nodes have outdegree 0.

Lemma 1.1 Let G = (V, E) be a computation graph with r + 1 input nodes {v_{0}, v_{1}, …, v_{r}} and t output nodes such that

• From any input node there is a path to some output node and

• to any output node there is a path from v_{0}.

Then |V | ≥ 2r + 1.

Proof: Let M ⊆ V be the set of nodes on paths from v_{0} to output nodes. To connect the remaining input nodes to output nodes there must be at least max{r − (|M| − 1), 0} non-input nodes outside M since each node in M, except v_{0}, has at least one of its predecessors from M. In total we get that |V | ≥ r + |M| + max{r − |M| + 1, 0} ≥ 2r + 1. □

Definition 1.2 Let A be an algorithm computing

S_{{1,2,...,k}}, S_{{2,3,...,k+1}}, …, S_{{n−k+1,n−k+2,...,n}}.

[figure: ⋯; x_{i}; x_{i+1}; ⋯]

Figure 1: The computation graph for the algorithm by Cooper and Kitchen [3].

The computation graph for A is the graph G_{A} = (V_{A}, E_{A}) such that for each S_{M} computed by A there is a corresponding node v_{M}. If A computes S_{M} as S_{M_{1}} ⊕ S_{M_{2}} then there are directed edges from v_{M_{1}} and v_{M_{2}} to v_{M}.

If the algorithm is optimal, the output nodes are exactly

v_{{1,2,...,k}}, v_{{2,3,...,k+1}}, …, v_{{n−k+1,n−k+2,...,n}}

corresponding to the values which are to be computed. The computation graph for the algorithm in [3] is shown in Figure 1.

Theorem 1.2 3\frac{k−1}{k+1}n − O(k) ≤ A(n, k) ≤ 3\frac{k−1}{k+1}n.

Proof: The upper bound was proved in [3]. Now let A be an optimal algorithm computing

S_{{1,2,...,k}}, S_{{2,3,...,k+1}}, …, S_{{n−k+1,n−k+2,...,n}}

and G_{A} its computation graph. Let 1 ≤ b ≤ n + 1 − 2k and consider a block B of nodes in V_{A}:

B = {v_{M} ∈ V_{A} | b ≤ min M ≤ b + k}.

We will show that |B| ≥ 4k − 2. The theorem follows since V_{A} can be split into ⌊\frac{n}{k+1}⌋ disjoint blocks and at least 3k − 3 of the nodes in each block are computation nodes.

[figure: x_{b}; x_{b+k}]

Figure 2: The division of a block of the computation graph in Figure 1 into “triangles”.

Notice that if (v_{M}, v_{M′}) ∈ E_{A} then

min M′ ≤ min M ≤ max M ≤ max M′.  (1)

The block B is divided into two “triangles” L and R (see Figure 2 for an example).

L = {v_{M} ∈ V_{A} | b ≤ min M ≤ max M < b + k},
R = {v_{M} ∈ V_{A} | b < min M ≤ b + k ≤ max M}.  (2)

In L there is a path from each of the k input nodes to the output node in L. Because of (1) above, all those paths lie inside L. Consequently |L| ≥ 2k −1. It remains to be proven that |R| ≥ 2k − 1 as well. Let G_{R} = (V_{R}, E_{R}) be a computation graph with V_{R} = R ∪ R′ where

R′ = {v_{M} ∈ V_{A} \ R | ∃v_{M′} ∈ R : (v_{M}, v_{M′}) ∈ E_{A}}

and E_{R} = E_{A} ∩ (V_{R} × V_{R}). R′ contains at least k −1 nodes from L since for each i in {b+1, b+2, …, b+ k − 1} there is a path from v_{{i}} (in L) to the output node v_{{i,i+1,...,i+k−1}} (in R) through nodes v_{M} with min M = i. R′ also contains at least k − 1 nodes outside L since for each j in {b + 2, b + 3, …, b + k} there is a path from v_{{j}} to the output node v_{{j,j+1,...,j+k−1}} (in R) through nodes v_{M} (outside L) with max M = j + k − 1 > b + k. By identifying v_{0} in Lemma 1.1 with v_{{b+k}} and v_{1}, v_{2}, …, v_{r} with R′ it follows that |V_{R}| ≥ 2|R′| + 1. Now |R′| ≥ 2(k − 1) implies that |R| = |V_{R}| − |R′| ≥ |R′| + 1 ≥ 2k − 1 as was to be proven. □

2 Set-maxima

In this section we examine the complexity of the problem for a constant k and a sequence (x_{1}, x_{2}, …, x_{n}) to compute the set-maxima

max{x_{i}, x_{i+1}, …, x_{i+k−1}}

for i = 1, 2, …, n − k + 1 [2, 4]. If the complexity is measured as the number of max operations required we already know the complexity from the previous section. We will use the model commonly used when measuring maxima problems, namely the decision tree model. That is, we count the number of comparisons needed to solve the problem at hand. Let C(n, k) be the number of comparisons needed to solve the set-maxima problem in the worst case. For simplicity, we assume throughout this section that no two elements in the sequence (x_{1}, x_{2}, …, x_{n}) are equal. Otherwise the ordering ≺ can be used where ≺ is defined by (x_{i} ≺ x_{j}) ⇔ [(x_{i} < x_{j}) ∨ ((x_{i} = x_{j}) ∧ (i < j))]. We also assume (x_{1}, x_{2}, …, x_{n}) to be given and fixed, so we will not continuously refer to it. We will repeatedly build lists of maxima for prefixes and suffixes for the various subsequences of the given sequence. The following notions turn out to be helpful, expressing what is going on.

Definition 2.1 Pref is the function that maps an interval [l, u] to the sorted list of indices (i_{1}, i_{2}, …, i_{m}) for maxima for prefixes of (x_{l}, x_{l+1}, …, x_{u}). Formally Pref is defined as:

Pref([l, u]) = (i_{1}, i_{2}, …, i_{m}) where l = i_{1} < i_{2} < ⋯ < i_{m} ≤ u and
i ∈ {i_{1}, i_{2}, …, i_{m}} ⇔ x_{i} = max{x_{l}, x_{l+1}, …, x_{i}}.

In analogy Suff is the function that maps an interval to the list of maxima for suffixes.

We call the problem of computing both Pref and Suff for an interval for the hump problem. Let H(n) be the number of comparisons needed to compute Pref([1, n]) and Suff([1, n]).

Another problem related to the set-maxima problem is the augmented staircase problem. This is the problem of computing Pref([1, n]) and in addition the second largest element. Let S(n) be the number of comparisons needed to solve the augmented staircase problem. The motivation for examining the hump and augmented staircase problem is Lemmas 2.1 and 2.2 to follow.

Lemma 2.1 S(n) ≤ H(n) + 1.

Proof: Assume Pref([1, n]) = (ℓ_{1}, …, ℓ_{p}) and Suff([1, n]) = (r_{q}, …, r_{1}) are known. Notice that ℓ_{p} = r_{q}. To solve the augmented staircase problem we only have to compute the second largest element. In general it is either x_{ℓ_{p−1}} or x_{r_{q−1}}. Which one is determined by one additional comparison. The special cases where p = 1 or q = 1 are easily dealt with and require no extra comparison. □

Lemma 2.2 For any 1 ≤ h ≤ k

\frac{H(h) + k − 1}{h + k − 2}n − O(k) ≤ C(n, k) ≤ \frac{H(k + 1) + ⌈log(k − 1)⌉}{k + 1}n + O(k).

Proof: We first show the upper bound for C(n, k). We partition the sequence (x_{1}, x_{2}, …, x_{n}) into blocks of size k + 1 and solve the hump problem for each block. This requires at most ⌈\frac{n}{k+1}⌉H(k + 1) comparisons. Then the set-maxima for the two subsequences of length k inside each block are known. The remaining set-maxima are maxima for subsequences intersecting two consecutive blocks. Let s_{k−1} ≥ s_{k−2} ≥ ⋯ ≥ s_{1} be the maxima of the suffixes of length k − 1, k − 2, …, 1 of a block and let p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{k−1} be the maxima of the prefixes of the next block. These values are known since the hump problem has been solved for each block. We have to compute max{s_{k−1}, p_{1}}, …, max{s_{1}, p_{k−1}} in order to compute the maxima for subsequences of length k intersecting the two blocks in question. Because the two sequences are monotone the outcome will be s_{k−1}, …, s_{i}, p_{k+1−i}, …, p_{k−1} for some i. We can determine i by binary search and therefore the k − 1 maxima by ⌈log(k − 1)⌉ additional comparisons for each pair of consecutive blocks. The upper bound follows.

[figure: x_{1}; ⋯; x_{n}; ; ; k − 2; h; H_{1}; H_{2}; H_{3}; H_{4}]

Figure 3: The ordering of the elements used by the off-line adversary strategy.

To show the lower bound we reduce a number of independent instances of the hump problem to the set-maxima problem. The idea is that if a subsequence of length h ≤ k is surrounded on both sides by subsequences of length k − 2 containing “small” elements, an algorithm solving the set-maxima problem will reveal which comparisons to make to solve the hump problem for the middle subsequence of length h. We partition the sequence (x_{1}, x_{2}, …, x_{n}) into blocks of size h + k − 2. The k − 2 leftmost elements in each block are “small” (think of them as being −∞). The rightmost h elements are “large”. By scaling, the “large” elements in each block are made greater than the elements in the blocks to the left of it. Figure 3 illustrates the set up. Besides solving all the hump problems any algorithm for the set-maxima problem has to verify that all the “small” elements are indeed small. Thus the number of comparisons made is at least (k−2)+H(h) per block except for the last one. We accounted for the k −2 and H(h). In addition, comparisons have to be made between the leftmost “large” element in a block and the the last (“large”) element in the preceeding block to determine the maximum for the subsequence of length k containing the two elements referred to and the “small” elements between them. All in all, at least H(h)+k −1 comparisons per block except for the last one have to be made. □ The optimal choice of h to maximise \frac{H(h)+k−1}{h+k−2} depends on H.

[figure: x_{1}; x_{l}; x_{i}; x_{j}; x_{r}; x_{n}]

Figure 4: A snapshot of the known ordering for the hump algorithm.

We finally prove two lemmas which lead to the main theorem of the paper, namely Theorem 2.5.

Lemma 2.3 H(n) ≤ n + 2\sqrt{n} − 2.

Proof: A simple way to solve the hump problem is to compute Pref([1, i]) from left to right and Suff([j, n]) from right to left by increasing i and decreasing j one by one and test whether a new maximum for a prefix or a suffix is met, until i and j meet (i = j − 1). In the extreme case only x_{1} and x_{n} are maxima and the situation when i and j meet after n − 2 comparisons would be that x_{1} and x_{n} had to be compared and the smaller of the two should be compared with up to \frac{n}{2} elements (those tested smaller than the larger one). This would altogether require \frac{3n}{2} − 1 comparisons. We can do much better by preventing this situation to happen. Let b be a constant to be fixed later. We augment the simple method by interrupting the propagation of i (and j) if no new maximum has been encountered for b steps. Let x_{l} be the last element in Pref([1, i]) and x_{r} the first element in Suff([j, n]) upon interruption. x_{l} and x_{r} are compared and if x_{l} is the smaller one, i is propagated until i and j meet or a new maximum is met. If x_{r} is the smaller one, j is propagated similarly. See Figure 4. Now when i and j meet at most b comparisons have to be made. To ensure this we did at most ⌊\frac{n−1}{b+1}⌋ interruptions and therefore at most ⌊\frac{n−1}{b+1}⌋ comparisons. We conclude that H(n) ≤ n − 2 + b + ⌊\frac{n−1}{b+1}⌋.

If we let b = ⌊\sqrt{n}⌋ − 1 we get H(n) ≤ n + ⌊\sqrt{n}⌋ + ⌊\frac{n−1}{⌊\sqrt{n}⌋}⌋ − 3 ≤ n + 2\sqrt{n} − 2,

and the lemma follows. □

Lemma 2.4 n + ⌊\sqrt{2n + \frac{1}{4}} − \frac{1}{2}⌋ − 3 ≤ S(n).

Proof: The bound is proved through an adversary argument. Divide (x_{1}, x_{2}, …, x_{n}) into b + 1 blocks of size a, b, b − 1, …, 2, 1 where a ≤ b. Then n = a + \frac{b(b+1)}{2} and b = ⌊\sqrt{2n + \frac{1}{4}} − \frac{1}{2}⌋. The blocks are named b + 1, b, b − 1, …, 2, 1. Notice that block b + 1 might be empty. Let ℓ_{i} denote the index of the leftmost element in block i for i = b, b − 1, …, 2, 1. The adversary strategy maintains b+1 parameters c_{b}, c_{b−1}, …, c_{1} and m such that the following invariant holds true during the computation.

• For b + 1 ≥ i > m, i > j, all elements in block i can be made smaller than all elements in block j.

• For m > i ≥ 1, all elements in block i can be made smaller than all elements in block m.

• For b ≥ i ≥ 1, the element x_{c_{i}} (the candidate in block i) can be made the maximal element within block i and if c_{i} ≠ ℓ_{i}, x_{ℓ_{i}} can be made the second largest element in block i.

• c_{m} = ℓ_{m}.

The invariant is depicted in Figure 5. The parameters are initialised such that each c_{i} is the leftmost element in block i, i.e.

(c_{b}, c_{b−1}, …, c_{1}; m) = (ℓ_{b}, ℓ_{b−1}, …, ℓ_{1}; 1).

It is quite involved to write down in detail the strategy to maintain the invariant. We describe the answers for the three cases where parameters change. For the remaining cases the answer follows from the invariant to be maintained. When x_{s} and x_{t} (s < t) from block i and j (i ≥ j) are compared, we call the comparison internal if i = j and external otherwise. The three cases described concern all situations where x_{s} is an element from a block to the left of block m (b ≥ i > m):

[figure: ⋯; x_{1}; x_{n}; ⋯; a; b; b − 1; m + 1; m; (m − 1) + ⋯ + 1; ; ; ; ; ; ]

Figure 5: The ordering of elements for the augmented staircase problem. The black points indicate the x_{c_{i}}’s.

A. b ≥ i > m and the comparison is internal (i = j), c_{i} = ℓ_{i} < s and at least one of x_{s} or x_{t} has not been compared to x_{c_{i}}. If x_{t} has not been compared to x_{c_{i}} then the answer given is x_{s} < x_{t} and c_{i} is changed to t. Otherwise the answer given is x_{s} > x_{t} and c_{i} is changed to s.

B. b ≥ i > m and the comparison is external (i > j), c_{i} = ℓ_{i} = s and some element x_{u} in block i has not lost any internal comparison. Then the answer given is x_{s} < x_{t} and c_{i} is changed to u.

C. b ≥ i > m and the comparison is external (i > j), c_{i} = ℓ_{i} and x_{c_{i}} has been compared to all the other elements in the block (and won), and no elements in the block have lost an external comparison. Then m is increased to i and the answer given is x_{s} > x_{t}.

Let L be the set of elements having lost at least twice during a computation. Then at least n + |L| − 1 comparisons have been made. It is known [6] that the second largest element has to be found among those elements which have only lost to the maximal one and that all but one of those have lost twice during any computation of the second largest (and largest) element. Let c_{b}, c_{b−1}, …, c_{1} and m be the parameters for the invariant at termination. It follows from the invariant that L contains max{0, m − 2} from block m since that many elements have lost to the maximal element.

In addition we will for each block to the left of block m identify an element in L. There are three cases:

1. Block i to the left of block m has been in situation A. Then the element in block i which lost when situation A occured is in L because it will eventually have lost twice.

2. Block i to the left of block m has been in situation B. Then at least two elements in block i have lost external comparisons. This is x_{ℓ_{i}} and x_{c_{i}}. Since i−1 internal comparisons in block i have been made, elements in block i have lost i + 1 times in total. Consequently one of the elements must belong to L.

3. Block i to the left of block m has not been in situation A or B (or equivalently c_{i} = ℓ_{i}). Consider the element x in block i which took part in an external comparison with an element to the right for the first time. x cannot be x_{c_{i}} since block i has not been in situation B or C (no block to the left of block m has been in situation C). So x ≠ x_{c_{i}} and x have lost both an internal and an external comparison. Thus x is in L.

It follows that |L| ≥ max{0, m − 2} + (b − m) and n + b − 3 comparisons are required. □ Combining Lemmas 2.2 (with h = k), 2.3, and 2.4 leads to rather involved expressions for the upper and lower bound for the set-maxima problem. We choose to give a simpler result. It is not optimal, and for small values of k it is far from being optimal.

Theorem 2.5

(1 + \frac{\sqrt{2k} − 5}{2(k − 1)}) n−O(k) ≤ C(n, k) ≤ (1 + \frac{2\sqrt{k + 1} + log(k − 1)}{k + 1}) n+O(k).

3 The on-line set-maxima problem

We define the on-line comparison complexity C_{on-line}(n, k) to be the number of comparisons needed for an on-line algorithm to solve the set-maxima problem. An on-line algorithm is required to read the sequence (x_{1}, x_{2}, …, x_{n}) from left to right and to know all set-maxima in (x_{1}, x_{2}, …, x_{i−1}) before reading x_{i}.

Lemma 3.1 C_{on-line}(n, k) ≤ ⌊(2 − \frac{1}{k−1}) n − 1⌋.

Proof: We are going to compute max{x_{i−k+1}, x_{i−k+2}, …, x_{i}} for i = k, k + 1, …, n (in that order). We do this by computing

Suff([1, 1]), Suff([1, 2]), …, Suff([1, k − 1])

and then Suff([i − k + 1, i]). The leftmost element in Suff([l, u]) is the maximal element in the interval [l, u]. Hence all set-maxima have been computed if we compute the Suff’s as described. Suff([l, u]) is represented by a double ended queue Q (this it what Knuth calls a deque [5]). When x_{i} is read and we go from interval [i − k, i − 1] to [i − k + 1, i], we first remove the leftmost index of Q if it is i − k. Now Q represents Suff([i − k + 1, i − 1]). Then we insert i into Q from the right. Before i is inserted, all indices are removed (from the right) which refer to values less than x_{i}. Now Q represents Suff([i − k + 1, i]) and the leftmost index refers to max{x_{i−k+1}, x_{i−k+2}, …, x_{i}} which is the new output. To count the number of comparisons involved we focus on how many comparisons any x_{i} can lose. It might lose one comparison when i is inserted into Q and again when i is removed. This immediately gives an upper bound 2n. During a computation Q represents interchangeably intervals of length k and k − 1. If we view a step as going from one interval [i − k + 1, i − 1] of length k − 1 to the next interval [i − k + 2, i] of length k − 1 by first inserting i from the right and then removing the leftmost index from Q if it equals i − k + 1. We can observe that each time the leftmost index in Q changes, it is either because x_{i} does not lose any comparisons during the insertion of i and i becomes the new leftmost index or it is because the index i − k + 1 is removed without x_{i−k+1} losing a comparison. In both cases one comparison is saved. Since Q cannot have the same leftmost index for k consecutive intervals of length k − 1, at least ⌈\frac{n}{k−1}⌉ − 1 comparisons are saved. Also x_{1} is inserted without losing and x_{n} is never removed. So

C_{on-line}(n, k) ≤ 2n − 2 − (⌈\frac{n}{k−1}⌉ − 1)

and the lemma follows. □

[figure: x_{1}; ⋯; x_{k}; ⋯; x_{n}]

Figure 6: The ordering enforced by the adversary strategy.

Lemma 3.2 (2 − \frac{1}{k−1}) n − O(k) ≤ C_{on-line}(n, k).

Proof: We use an adversary strategy which on x_{i}?x_{j} for i < j answers:

x_{i} > x_{j} if k − 1 divides i, and x_{i} < x_{j} otherwise.

The ordering that we enforce on (x_{1}, x_{2}, …, x_{n}) can be seen in Figure 6. Let 1 < p and (p + 2)(k − 1) ≤ n. We argue that k − 1 elements

x_{p(k−1)+1}, x_{p(k−1)+2}, …, x_{(p+1)(k−1)}

will lose at least 2k − 3 comparisons altogether. Having argued that, the lemma follows. Since x_{p(k−1)} = max{x_{(p−1)(k−1)+i}, …, x_{p(k−1)+i}} for i = 1, 2, …, k − 1 any on-line algorithm has to compare x_{p(k−1)+i} to x_{p(k−1)} where x_{p(k−1)+i} loses. Since x_{(p+1)(k−1)} = max{x_{p(k−1)+1}, …, x_{(p+1)(k−1)+1}} it has to be verified that x_{p(k−1)+i} < x_{(p+1)(k−1)} for i = 1, 2, …, k − 2. This cannot follow by transitivity from the comparisons involving x_{p(k−1)} above. Thus x_{p(k−1)+i} has to lose at least once more (for 1 ≤ i < k − 1) and the statement follows. □ The following theorem is a direct corollary of Lemmas 3.1 and 3.2.

Theorem 3.3 C_{on-line}(n, k) = (2 − \frac{1}{k−1}) n − O(k).

References

[1] A. E. Andreev. On a family of boolean matrices. Moscow Univ. Math. Bull., 41(2):97–100, 1986.

[2] Amotz Bar-Noy, Rajeev Motwani, and Joseph Naor. A linear time approach to the set maxima problem. SIAM Journal on Discrete Mathematics, 5(1):1–9, 1992.

[3] James Cooper and Leslie Kitchen. CASOP: A fast algorithm for computing the n-ary composition of a binary associative operator. Information Processing Letters, 34:209–213, 1990.

[4] Wayne Goddard, Claire Kenyon, Valerie King, and Leonard J. Schulman. Optimal randomized algorithms for local sorting and set-maxima. SIAM Journal of Computing, 22(2):272–283, 1993.

[5] Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, Reading, MA, 1968.

[6] Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading, MA, 1973.

[7] Kurt Mehlhorn. Some remarks on boolean sums. ACTA Informatica, 12:371–375, 1979.

[8] Ingo Wegener. Boolean functions whose monotone complexity is of size n^{2}/log n. Theoretical Computer Science, 21:213–224, 1982.

Recent Publications in the BRICS Report Series

RS-96-42 Gerth St�lting Brodal and Sven Skyum. The Complexity of Computing the k-ary Composition of a Binary Associative Operator. November 1996. 15 pp.

RS-96-41 Stefan Dziembowski. The Fixpoint Bounded-Variable Queries are PSPACE-Complete. November 1996. 16 pp. Presented at the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.

RS-96-40 Gerth St�lting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan. The Randomized Complexity of Maintaining the Minimum. November 1996. 20 pp. To appear in a special issue of Nordic Journal of Computing devoted to the proceedings of SWAT ’96. Appears in Karlson and Lingas, editors, Algorithm Theory: 5th Scandinavian Workshop, SWAT ’96 Proceedings, LNCS 1097, 1996, pages 4�15.

RS-96-39 Hans H� uttel and Sandeep Shukla. On the Complexity of Deciding Behavioural Equivalences and Preorders � A Survey. October 1996. 36 pp.

RS-96-38 Hans H� uttel and Josva Kleist. Objects as Mobile Processes. October 1996. 23 pp.

RS-96-37 Gerth St�lting Brodal and Chris Okasaki. Optimal Purely Functional Priority Queues. October 1996. 27 pp. To appear in Journal of Functional Programming, 6(6), December 1996.

RS-96-36 Luca Aceto, Willem Jan Fokkink, and Anna Ing� olfsd� ottir. On a Question of A. Salomaa: The Equational Theory of Regular Expressions over a Singleton Alphabet is not Finitely Based. October 1996. 16 pp.

RS-96-35 Gian Luca Cattani and Glynn Winskel. Presheaf Models for Concurrency. October 1996. 16 pp. Presented at the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.