You got 2^N as time limit by assuming that # of elements will be doubled in each step i.e. adding and subtracting given number from each element in the array.
But observe that all elements should be be between min and max. Hence the # of distinct elements can be at most (max - min). Any element < min or > max after addition/subtraction can be ignored.
Thus # of operations are N*(max - min) rather than 2^N
Read more… (81 words)