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.

Your question seems strange.
You are asking about the relevance of an O(n) solution
to a problem which requires an O(n) solution.

--
pete
.

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)