Algorithms for testing occurrences of length 4 patterns in permutations

In this paper linear time sequential and optimal parallel algorithms for testing pattern involvement for all length 4 permutations are described. This is an improvement as the previous best sequential algorithms, for most of these pattern require (O(nlog n)) time. Our parallel algorithms can be implemented in (O(log n)) time with (n/log n) processors on the CREW PRAM model, or alternatively in (O(log log log n)) time with (n/log log log n) processors on a CRCW PRAM PRAM model. Parallel algorithm can also be implemented in constant time with (nlog ^3 n) processors on a CRCW PRAM model. The previous best parallel algorithms were available for only some of these patterns and took (O(log n)) time with n processors on the CREW PRAM model.