AN Ω( log n−k log k) TIME LINEAR COST LOWER BOUND FOR THE k FUNCTIONS COARSEST PARTITION PROBLEM
Clive N. Galley · Parallel Processing Letters · 1996
We consider the k functions coarsest partition problem for a set S, where |S|=n, and k functions from S to S. We present an Ω(log n−k log k) time, linear work, lower bound for this problem on the CRCW PRAM model of computation.