Effect of Parallelism on the Efficiency of Binary Tree Search

Abstract

Let \(T_n\) denote a complete binary tree of depth \(n\). Each internal node \(v\) of \(T_n\) has two children denoted by \(\text{left}(v)\) and \(\text{right}(v)\). Let \(f\) be a function mapping each internal node \(v\) to \(\{\text{left}(v), \text{right}(v)\}\). This naturally defines a path from the root, \(\lambda\), of \(T_n\) to one of its leaves given by

\[\lambda, f(\lambda), f^2(\lambda), \ldots f^n(\lambda).\]

We consider the problem of finding this path via a deterministic algorithm that probes the values of \(f\) in parallel. We show that any algorithm that probes \(k\) values of \(f\) in one round requires \(\frac{n}{\lfloor \log(k+1) \rfloor}\) rounds in the worst case. This indicates that the amount of information that can be extracted in parallel is, at times, strictly less than the amount of information that can be extracted sequentially.