Time-complexity of nested for loop

algorithmsbig o

I have loops like this:

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) {
        sum += 1;
    }
}

It's O(n * ), but I'm not sure what the j < i loop is.

I have some tests that I ran,

n = 10, runs = 45

n = 20, runs = 190

n = 40, runs = 780

n = 80, runs = 3160

n = 10, runs = 12720

It seems to be converging onto .5*n^2, but I'm not quite sure.

Best Answer

You are summing up the numbers from 1 to n, incrementing the value by one each time. This is essentially the classic Gauss sumation which is:

sum(1 .. n) = (n * n-1)/2

This also happens to be the number of times through the loop.

(n^2 - n) / 2
(n^2)/2 - n/2

When representing Big O, only term with the highest power is used and constants are thrown away, and thus the answer is O(n²).

More about this particular problem can be read on CS.SE at Big O: Nested For Loop With Dependence

Related Solutions

Big O Notation – Average Time Complexity of Algorithms

f ∈ Θ(g)

is the same as

f ∈ Ο(g) ∧ f ∈ Ω(g)

So, if you can prove that f ∈ Ο(g) ∧ f ∈ Ω(g), then by all means use Θ.

Note that this has absolutely nothing whatsoever to do with time complexity of algorithms, average or otherwise. Θ, Ο, ο, Ω and ω are about the growth rate of functions; whether those functions describe average time/step/space complexity of an algorithm, worst-case time/step/space complexity of an algorithm, best-case time/step/space complexity of an algorithm, expected case time/step/space complexity of an algorithm, the population of China, the number of users on StackOverflow, or the size of Lara Croft's bra is completely irrelevant.

Algorithms – Complexity in Nested Loops

You seem to think that the complexity of an algorithm is linked to the number of nested loops. It is not the case. The following piece of code is O(1):

for i in [1.. 10^15]:
    for j in [1.. 10^15]:
        for k in [1.. 10^15]:
            dosomethingO1()

Complexity is related to the rate of growth of the number of operations. Unrolling your loop does not change that. So:

foreach(element in myArray) {
    doSomeAction(element);
}

Has 0(1) if the number of elements in myArray is bounded. The complexity will be decided by the number of iterations in the while loop.

About your grid example: if n is the number of cells and your grid is represented as a nested array, looping over those arrays still yields O(n) complexity.

Best Answer

Related Solutions

Big O Notation – Average Time Complexity of Algorithms

Algorithms – Complexity in Nested Loops

Related Topic