Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
$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
2  
Big O in general does not tell you about real-world suitability. –  sdcvvc Dec 13 '12 at 14:48
add comment

1 Answer

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.

share|improve this answer
    
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. –  Shahmohamamdi Dec 13 '12 at 17:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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