CODEWITHSUNDEEP
javabig-operformance
Tom W
Tom W

Reputation: 578

Big O for a nested series of for loops

I've got a question about calculating Big O running times for a series of loops, that are nested in an outer for loop.

For example:


for (50,000 times)
{
    for (n times)
    {
        //Do something
    }
    for (n-2 times)
    {
        //Do something
    }
    for (n times)
    {
        //Do something
    }
    for (n-2 times)
    {
        //Do something
    }
}

The outer loop is a constant, so I think that is ignored. Is it then as easy as doing the following calculation?

N + N-2 + N + N-2

2N + 2(N-2)

4N - 4

O(4N - 4)

O(4N) - after removing the -4 constant

Is this correct?

Thanks.

Upvotes: 5

Views: 765

Answers (3)

Shuo
Shuo

Reputation: 4847

This is O(N). But in this context, depending on what you have for N, the constant might have a big impact on the performance of your algorithm.

Upvotes: 0

fastcodejava
fastcodejava

Reputation: 41127

This is correct. You are just adding four loops which is O(N). So it is 4O(N), then it is multiplied by 50, 000 which is a large number but it is not N dependent.

Upvotes: 0

Thorbjørn Ravn Andersen
Thorbjørn Ravn Andersen

Reputation: 75426

This is O(n)

(you are only interested in what is the "largest" part of the equation, and you strip the constant).

If you had a loop i from 1..n and another loop inside j from i..n, it would be O(n^2).

Upvotes: 6

Related Questions