Parallel algorithms for finding the nmeasure of the union of intervals


Ivan Stojmenović, Lidija Čomić




The paper presents an algorithm for finding the measure of the union of intervals. The algorithm is based on, a divide-and-conquer approach. When implemented on a sequential computer it runs in optimal $O(n^*\log(n))$ time. The algorithm is modified for several parallel models of computations. The running time of the algorithm on mesh-connected parallel computers is optimal $O(n^{**}(l/2))$, while the running times on a concurrent read exclusive write PRAM and concurrent read concurrent write PRAM are $O(\log^{**}2(n))$ and $O(\log(n))$ respectively, which is very efficient.