# A question about parallel algorithm complexity

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.

-
$n$-exponential probability probably means that the algorithm could fail, but this happens with probability $c^n$ for some $c < 1$. – Yuval Filmus Dec 13 '12 at 12:13
As for the other question, $n$ could be either the number of processors or some complexity measure of the input. In the former case, to implement an algorithm with $n=10^5$ you will need $10^5$ cores. Do you have any particular algorithm in mind? – Yuval Filmus Dec 13 '12 at 12:14
Big O in general does not tell you about real-world suitability. – sdcvvc Dec 13 '12 at 14:48

You have an algorithm that can be represented as $O(n \log n)$ units of work each taking constant time or as $O(n)$ units of work each taking $O(\log n)$ time. Here $n$ is a parameter that characterizes the size of the problem.