Why the O(n^2) solution is also getting accepted?


#1

Why the O(n^2) solution is also getting accepted?


#2

Your solution probably wasn’t O(n^2).

If you decided to iterate from the last number to the first and for every iteration iterate from the current number to the first then that solution is actually O(n) although it has two loops. N - 1 + N - 2 … 3 + 2 + 1 is still O(n).


#3

Your time complexity analysis is incorrect:

1+2+…+N=N*(N+1)/2;

1+2+…+N-1=(N-1)*N/2;

So, the solution of iterating from last number and checking for every number pair with the current number is actually O(N^2).