O(1) sum

Biotronic via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Sun Jun 11 23:15:07 PDT 2017


On Monday, 12 June 2017 at 01:36:04 UTC, Stefan Koch wrote:
> On Monday, 12 June 2017 at 01:02:58 UTC, helxi wrote:
>> Is it possible to sum an array in O(1)?
>
> No.
> If you want to sum the elements you have to at-least look at 
> all the elements.
> So it'll always be O(N).
> it's the best you can do.

On a multi-core system we can do better:

auto nums = iota(10_000_000.0f);
auto sum = taskPool.reduce!"a + b"(nums);

Given arbitrary parallelism (yeah, right!), this will be 
O(log(N)). For real-world systems, it might give a speed-up for 
large arrays, but won't reduce the big-O complexity. Of course, 
there will also be overhead to such a solution, so there is a 
limit to how much one'd actually benefit from it.

--
   Biotronic


More information about the Digitalmars-d-learn mailing list