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
