This algorithm does not have a quadratic run time right?

I recently had an interview and was given a small problem that I was to code up.

The problem was basically find duplicates in an array of length n, using constant space in O(n). Each element is in the range 1-(n-1) and guaranteed to be a duplicate. This is what I came up with:

public int findDuplicate(int[] vals) {
    int indexSum=0;
    int valSum=0;   
    for (int i=0; i< vals.length; i++) {
         indexSum += i;
  开发者_开发问答       valSum += vals[i];
    }
    return valSum - indexSum;
}

Then we got into a discussion about the runtime of this algorithm. A sum of series from 0 -> n = (n^2 + n)/2 which is quadratic. However, isn't the algorithm O(n) time? The number of operations are bound by the length of the array right?

What am I missing? Is this algorithm O(n^2)?

The fact that the sum of the integers from 0 to n is O(n^2) is irrelevant here.

Yes you run through the loop exactly O(n) times.

The big question is, what order of complexity are you assuming on addition?

If O(1) then yeah, this is linear. Most people will assume that addition is O(1).

But iwhat if addition is actually O(b) (b is bits, and in our case b = log n)? If you are going to assume this, then this algorithm is actually O(n * log n) (adding n numbers, each needs log n bits to represent).

Again, most people assume that addition is O(1).

Algorithms researchers have standardized on the unit-cost RAM model, where words are Theta(log n) bits and operations on words are Theta(1) time. An alternative model where operations on words are Theta(log n) time is not used any more because it's ridiculous to have a RAM that can't recognize palindromes in linear time.

Your algorithm clearly runs in time O(n) and extra space O(1), since convention is for the default unit of space to be the word. Your interviewer may have been worried about overflow, but your algorithm works fine if addition and subtraction are performed modulo any number M ≥ n, as would be the case for two's complement.

tl;dr Whatever your interviewer's problem was is imaginary or rooted in an improper understanding of the conventions of theoretical computer science.

You work on each on n cells one time each. Linear time.

Yes the algorithm is linear*. The result of valSum doesn't affect the running time. Take it to extreme, the function

int f(int[] vals) {
   return vals.length * vals.length;
}

gives n² in 1 multiplication. Obviously this doesn't mean f is O(n²) ;)

^{(*: assuming addition is O(1))}

The sum of i from i=0 to n is n*(n+1)/2 which is bounded by n^2 but that has nothing to do with running time... that's just the closed form of the summation.

The running time of your algorithm is linear, O(n), where n is the number of elements in your array (assuming the addition operation is a constant time operation, O(1)).

I hope this helps.
Hristo