Re: searching for missing element in an array

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

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: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)