Confusion with the Running Time of an algorithm that finds duplicate character I have the following simple algorithm to find duplicate characters in a string:

for i = 1 -&gt; n
    for j = i + 1 -&gt; n
        if A[i] == A[j] return true
return false 


Why is the running time of this algorithm $\mathcal{O}(n^2)$?
If the first iteration is $n$ steps then, $n-1, n-2,n-3,..,1$ it seems to me that 
adding all these would never be $n^2$ or am I wrong?
When we sum all numbers we get $n(n-1)/2$, which is in the class of functions $O(n^2)$. Make sure that you understand what big O notation is about.

Another way of seeing that this sum is $O(n^2)$ since each summand is at most $n$ and there are at most $n$ summands, so the sum is at most $n^2$.