Advanced Algorithm Q.23

0. Suppose we have three sorting algorithms X1, X2, and X3 on PRAMs.
X1 runs in O(log n) time using nlog n processors.
X2 runs in O(log2 n) time using n/log n processors.
X3 runs in O(log n log log n) time using n/log n processors.
Which of the algorithms is/are optimal?

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *