What's the complexity of these two for-loops?

Question

What's the time complexity of this algorithm? My initial guess is that it's O(log[n])?

int array[] = new int[100];
int counter = 0;

for ( int i = 0; i < array.length; i++ ) {
    for ( int j = i + 1; j < array.length; j++ ) {
        if ( array[i] == array[j] ) {
            counter++;
        }
    }
}

lmgify http://stackoverflow.com/questions/15433435/calculate-the-complexity-of-a-nested-for-loop — MrSimpleMind, Sep 15 '13 at 11:41

score 3 · Answer 1 · answered Sep 15 '13 at 11:41

3

The if part in your code gets executed about 1 + 2 + 3 +...+ n times (n - i - 1 where i = 0...n - 1, which is equal to 0,5*n*(n+1) which is O(n^2).

answered Sep 15 '13 at 11:41

Mateusz

3,038
4
27
41

score 2 · Accepted Answer · answered Sep 15 '13 at 11:39

2

Nope. This is O(N^2).

Look here section 4 under "How to Determine Complexities"

answered Sep 15 '13 at 11:39

giorashc

13,691
3
35
71

score 0 · Answer 3 · answered Sep 15 '13 at 11:42

There are two possible answers. The technically correct one is O(1), because the array has a constant length, so the number of inner loop iterations is a constant.

If we assume instead that the array is length n, then the numbers of iterations of the inner loop are n-1, n-2, n-3, ... , 1, 0. The sum of an arithmetic series of length n, starting at 0, is O(n^2).

score 0 · Answer 4 · answered Sep 15 '13 at 13:54

0

The order is O(n^2).

Explanation: Suppose the array length is n.
Then for iteration of first loop:
There will n-2 iterations of second loop.
so total time will be: (n-2)+(n-2)+............(n-2) //for n-1 times
which will be: (n-1)*(n-2).

answered Sep 15 '13 at 13:54

user2779780

41
5

score 0 · Answer 5 · answered Mar 17 '14 at 15:09

0

A formal way to deduce the time complexity of your algorithm:

enter image description here

answered Mar 17 '14 at 15:09

Mohamed Ennahdi El Idrissi

2,931
2
19
32

What's the complexity of these two for-loops?

5 Answers5