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 execpted result. Tried with some parrallel loop but not conclusive too.
Thank's for your help
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.