Let P be an algorithm for solving a problem Π on CRCW-PRAM(p). According to Theorem2.1, the execution of P on EREW-PRAM(p) will be at most O(log p)-times slower than on CRCW-PRAM(p). Now suppose that...

Let P be an algorithm for solving a problem Π on CRCW-PRAM(p). According to Theorem2.1, the execution of P on EREW-PRAM(p) will be at most

O(log p)-times slower than on CRCW-PRAM(p). Now suppose that p =

poly(n), where n is the size of a problem instance. Prove that log p = O(log n).