# 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 -> n
for j = i + 1 -> 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?

• Because 1+2+3+...+n = (n+1)*(n/2) = O(n^2) – Roi Divon Apr 13 '14 at 20:39
• It seems to me you don't know what $O(n^2)$ means exactly. For example, it is perfectly correct to say the runtime of your algorithm is $O(n^4)$. Check out the answers linked to here. – Juho Apr 13 '14 at 22:07

Don't confuse the $n$ in $O(n)$ with the $n$ in your algorithm! If you consider the number of times the line if A[i] == A[j] return true is evaluated, this will in the worst case indeed be $(n-1) + (n-2) + (n-3) + \dots + 1$. There is a closed formula for this sum:

$\sum _{i=1}^n i = \frac{n(n+1)}{2} = \frac{n^2 + n }{2}$, (see Wiki)

so asymptotically you get the runtime of $O(n^2)$.

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

• Beginners, keep in mind that $A \leq n^2 \implies A \in O(n^2)$ but not the other way around. – Raphael Apr 14 '14 at 8:04

The inner loop is executed $\sum_{1\le i\le n}\sum_{i\lt j\le n} 1$ times. $$\sum_{1\le i\le n}\sum_{i\lt j\le n} 1=\sum_{1\le i\lt j\le n} 1=\sum_{1\le j\le n}\sum_{1\le i\le j-1}1=\sum_{1\le j\le n}(j-1)$$ $$=0+\dots+n-1=(n-1)n/2.$$

This is $\cal O(n^2)$.