CODEWITHSUNDEEP
multithreadingalgorithmtime-complexitycomplexity-theory
Mutmut
Mutmut

Reputation: 13

Can we get a better complexity than O(n) for cumulative sum while using multithreading?

I'm new to multithreading algorithms and I'm trying do recode cumulative sum function to get a better complexity than O(n).

Have you any hint? Or we can't get better than O(n)?

I tried to use divide and conquer method but didn't get the expected result. Tried with some parallel loop but not conclusive too.

Thanks for your help

Upvotes: 1

Views: 151

Answers (2)

orlp
orlp

Reputation: 117771

Wikipedia contains several parallel prefix sum algorithms, including one which runs in O(n log n / k) time if you have k parallel processors, which means the overall process can be O(log n) if you have n processors.

Upvotes: -2

zmccord
zmccord

Reputation: 2612

Well, very approximately speaking, if you have k cores and a very parallelizable problem (which this is), then you ought to be able to divide your time taken by k with parallelism.

Problem is, k is fixed, while n isn't. With k being constant, O(n/k) is the same thing as O(n). It'll go faster, but not asymptotically faster.

In abstract principle, your divide-and-conquer algorithm might well run in O(log(n)) time, but it would require O(n) processors to do so.

Because k is fixed, multithreading an algorithm will never improve its asymptotic time, only the constant factors. Your parallel implementation might finish in one tenth the time or one twentieth the time the single-threaded implementation does, but not in log of the time or square root of the time.

Upvotes: 9

Related Questions