###
Finding all nearest smaller values on a distributed memory machine

Jyrki Katajainen

Department of Computer Science,
University of Copenhagen,
Universitetsparken 1,
DK-2100 Copenhagen East, Denmark

jyrki@diku.dk

#### Abstract

Let $A = [a_j]_{j=1}^{n}$ be a sequence of $n$ elements drawn from some
totally ordered set. In the all nearest smaller values problem
the task is to find for each $a_j, j \in \{1,2,\ldots,n\}$, the
elements $a_i$ and $a_k$ such that $i=\max\{h\in \{1,\ldots,j\}
\mid a_h < a_j\}$ and $k=\min\{h\in \{j,\ldots,n\} \mid$ $a_h < a_j\}$,
if such elements
exist.
In this paper it is shown that this problem can be solved
in $O(n/q)$ time and $O(n)$ space with $q$ processors
on a distributed memory machine, provided that
$q \in \{1,2,\ldots,O(n/\log_2 n)\}$. More
precisely, the machine considered consists of $q$ processors and $q$
memory modules connected by a communication network, which
allows every processor to access any memory module in constant
time if only every memory module is accessed by at most one
processor at a time.
The result proved complements the earlier known results showing that, on
a CREW PRAM, $\Omega(\log_2 n)$ is a lower bound for the time
complexity of the problem with any number of processors and that,
on a hypercube, any $O(\log_2 n)$ algorithm must use
$\Omega(n)$ processors.

Conference Home Page