CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
Jack Twain
Jack Twain

Reputation: 6372

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

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++;
        }
    }
}

Upvotes: 0

Views: 139

Answers (5)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

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

enter image description here

Upvotes: 0

user2779780
user2779780

Reputation: 41

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

Upvotes: 0

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

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

Upvotes: 0

Mateusz
Mateusz

Reputation: 3048

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

Upvotes: 3

giorashc
giorashc

Reputation: 13713

Nope. This is O(N^2).

Look here section 4 under "How to Determine Complexities"

Upvotes: 2

Related Questions