Re: searching for missing element in an array

Juha Nieminen wrote:
Ico wrote:
Juha Nieminen <nospam@xxxxxxxxxxxxxx> wrote:
Ico wrote:
For example, can you tell in advance what the sum of all
numbers [1..n] is, without actually adding them all up ?
I fail to understand how that is relevant to the problem in question.
Yes, being able to calculate the sum of integers 1-n without doing an
explicit loop is faster, but it doesn't change the O(n) complexity of
the requested algorithm.
See rossum's reply, he explains the algorithm there.

That didn't answer my question. His algorithm is still O(n) regardless
of whether you calculate the sum of integers between 1 and n with a
mathematical formula or in a loop.

The algorithm that involves summing doesn't purport to be more efficient
than O(n). Asking whether there is an easy way to find sum(1..n) without
adding them all up does not imply that this ability solves the problem
in an especially quick manner. It is just a question meant to spur
thought about a way to solve the problem which is really simple and
easy to implement.

- Logan
.

Relevant Pages

  • Re: searching for missing element in an array
    ... I fail to understand how that is relevant to the problem in question. ... being able to calculate the sum of integers 1-n without doing an ... explicit loop is faster, but it doesn't change the Ocomplexity of ... the requested algorithm. ...
    (comp.programming)
  • Re: searching for missing element in an array
    ... I fail to understand how that is relevant to the problem in question. ... explicit loop is faster, but it doesn't change the Ocomplexity of ... the requested algorithm. ...
    (comp.programming)
  • Re: searching for missing element in an array
    ... I fail to understand how that is relevant to the problem in question. ... being able to calculate the sum of integers 1-n without doing an ... explicit loop is faster, but it doesn't change the Ocomplexity of ... he explains the algorithm there. ...
    (comp.programming)