2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Because 1+2+3+...+n = (n+1)*(n/2) = O(n^2) $\endgroup$ – Roi Divon Apr 13 '14 at 20:39
  • 4
    $\begingroup$ 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. $\endgroup$ – Juho Apr 13 '14 at 22:07
1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.