CODEWITHSUNDEEP
javaalgorithm
mzz
mzz

Reputation: 121

What is the complexity of empty for loop?

I was wondering if the complexity of a empty for loop like below is still O(n^2)

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

update : changed height and width variable to n

Upvotes: 6

Views: 1739

Answers (7)

Tasnim Zotder
Tasnim Zotder

Reputation: 1

It depends on the compiler. Theoretically, it's O(n), where n is the number of loops, even if there's no task inside the loop.

But, in case of some compiler, the compiler optimizes the loop and doesn't iterates n times. In this situation, the complexity is O(1).

For the loop mentioned above, it's both O(n) and O(n^2). But, it's good practice to write O(n^2) as Big O covers upper bound.

Upvotes: 0

user5941056
user5941056

Reputation:

The nested loop performs constant work O(1) n times, so nO(1)=O(n)O(1)=O(n).

The external loop performs the above mentioned O(n) work n times so nO(n)=O(n)O(n) =O(n^2).

In general:``

  • f(n) ∈ O(f(n))
  • cf(n) ∈ O(f(n)) if c is constant
  • f(n)g(n) ∈ O(f(n)g(n))

Upvotes: 0

Ihar Yudziankou
Ihar Yudziankou

Reputation: 108

Big O is just an approximation for evaluating count of steps in algorithm. We could have formulas for exact count of steps in algorithm, but they are complex and difficult to realise the actual complexity.

1) O(0.000 000 001*n^2 - 1 000 000 000) = n^2

2) O(1 000 000 000*n ) = n

Despite of Big O first case is less e.g. for N = 0..1 000 000

More than, it doesn't take into account how fast particular step.

So, your loop is a case when O(n^2) could be less than O(1)

Upvotes: 0

Dorkmania
Dorkmania

Reputation: 962

Based off of my understanding of time-complexity of an algorithm, we assume that there are one or more fundamental operations. Re-writing the code using a while loop and expanding for logic :

int i = 0, j = 0;

while(i < n)
{
    while(j < n)
    {
        ; //nop or no-operation
        j = j + 1; // let jInc be alias for j + 1  
    }
    i = i + 1;  // let iInc be alias for i + 1
}

Now if your objective is to perform a 'nop' n^2 times, then the time complexity is O(0) where 'nop' is the fundamental operation. However, if the objective is to iterate 2 counters ('i' and 'j') from 0 to n -1 or count n^2 times then the fundamental operations can be addition (j + 1 and i + 1), comparison (i < n and j < n) or assignment (i = iInc and j = jInc) i.e. O(n^2).

Upvotes: 0

M.Maxim
M.Maxim

Reputation: 9

Pay attention, you can do something else than i++, e.g. fun(i).

Upvotes: 0

Szab
Szab

Reputation: 1263

If it won't get optimized out by the compiler, the complexity will still be O(n^2) (or actually O(N*M)) - even though the loops bodies are empty, the condition checks and incrementation of both counters are still valid operations which have to be performed.

Upvotes: 7

Pritam Banerjee
Pritam Banerjee

Reputation: 18933

The complexity of any for loop that runs from 1 .. n is O(n), even if it does not do anything inside it. So in your case it is always going to be O(n^2) irrespective of what you are doing inside the loops.

Here in your example i and j are running till n and hence individually depends on the value of n making the the nested for loops having a complexity of O(n^2)

Upvotes: 3

Related Questions