Re: searching for missing element in an array

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.

--
:wq
^X^Cy^K^X^C^C^C^C
.

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. ... 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
    ... Ico wrote: ... I fail to understand how that is relevant to the problem in question. ... but it doesn't change the Ocomplexity of ... the requested algorithm. ...
    (comp.programming)