Is it possible to sum an array in O(1)?

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 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

On Monday, 12 June 2017 at 06:15:07 UTC, Biotronic wrote:
> 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

Biotronic how do you arrive at  O(log(N)) ??
And which logarithm  ?

On 06/11/2017 06:02 PM, helxi wrote:
> Is it possible to sum an array in O(1)?

It's possible to maintain the sum as elements are added and removed. Then, accessing it would be O(1).

Ali

On Mon, Jun 12, 2017 at 06:16:06PM +0000, Stefan Koch via Digitalmars-d-learn wrote:
> On Monday, 12 June 2017 at 06:15:07 UTC, Biotronic wrote:
[...]
> > 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
> 
> Biotronic how do you arrive at  O(log(N)) ??
> And which logarithm  ?

His stated presupposition is arbitrary parallelism, which I assume means arbitrary number of CPUs or cores that can run in parallel, so then you can divide the array of N elements into N/2 pairs, sum each pair in parallel, which gives you N/2 subtotals after one iteration, then you recursively repeat this on the subtotals until you're left with the final total. The complexity would be O(log_2(N)) iterations, assuming that the constant factor hidden by the big-O covers the overhead of managing the parallel summing operations across the arbitrary number of cores.

You can also get logarithms of a different base if you divided the initial array, say, into triplets or j-tuplets, for some constant j. Then you'd get O(log_j(N)). (Of course, with a slightly larger constant factor, assuming that each CPU core only has binary summation instructions. But if your instruction set has multiple-summation instructions you may be able to get a higher j at little or no additional cost. Assuming you can produce a machine with an unlimited number of cores in the first place.)

Of course, his comment "yeah, right!" indicates that he's aware that this is an unrealistic scenario. :-)


T

-- 
Notwithstanding the eloquent discontent that you have just respectfully expressed at length against my verbal capabilities, I am afraid that I must unfortunately bring it to your attention that I am, in fact, NOT verbose.