When in a Parallel algorithm we say:This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $n$-exponential probability.Then Can we Implement this algorithm for a Quad-Core Computer (and just 4 threads) with $n=100,000$?The other question is what is the $n$-exponential probability in this sentence?Thanks.
A question about parallel algorithm complexity
algorithm analysis;runtime analysis;parallel computing