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?


  • $\begingroup$ $n$-exponential probability probably means that the algorithm could fail, but this happens with probability $c^n$ for some $c < 1$. $\endgroup$ – Yuval Filmus Dec 13 '12 at 12:13
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Dec 13 '12 at 12:14
  • 2
    $\begingroup$ Big O in general does not tell you about real-world suitability. $\endgroup$ – sdcvvc Dec 13 '12 at 14:48

You are probably in the realm of asynchronous parallel computations where units of work are performed by processors at their pace and communication is performed explicitly. This model is a good approximation to many real life parallel computers such as PC clusters or multicore CPUs.

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.

The units of work can be executed on a parallel computer with a fixed number of sequential processing elements (e.g. processor cores). It depends on the algorithm whether the work units can complete while other work units have not started, or whether the computations will have to interleave.

In a practical computer interleaving can be achieved through pre-emption and context switches.

| cite | improve this answer | |
  • $\begingroup$ Thank all. I asked the first question to Know if this algorithm is a real-world suitability or not? if there is another implementable (a real-world suitability) algorithm, and has not O(1) running time, which one is better? in other words I want know how to compaire this whit others. is O(1) running time denote to be a good algorithm? again thanks. $\endgroup$ – Shahmohamamdi Dec 13 '12 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.