CODEWITHSUNDEEP
algorithmfor-looptime-complexity
domino
domino

Reputation: 99

two or more for loops time complexity

If we assume the statements inside of a for loop is O(1).

for (i = 0; i < N; i++) {
    sequence of statements
}

Then the above time complexity should be o(n) another example is:

for (i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
        sequence of statements
    }
}

the above time complexity should be o(n^2)

It seems like one for loop symbolize n times However, I've seen some discussion said that it's not simply like this Sometimes there are 2 for loops but it doesn't mean the time complexity must be o(n^2)

Can somebody give me an example of two or more for loops with only O(n) time complexity (with explanation will be much better)???

Upvotes: 0

Views: 648

Answers (2)

Guy Gastineau
Guy Gastineau

Reputation: 121

Loops can have fixed time if the bounds are fixed. So for these nested loops, where k is a constant:

// k is a constant
for (int i=0; i<N; i++) {
  for (int j=0; j<k; j++) {
  }
}

// or this
for (int i=0; i<k; i++) {
  for (int j=0; j<N; j++) {
  }
}

Are both O(kN) ~= O(N)

The code in the post has a time complexity of:

enter image description here

Given this is a second order polynomial, (N^2 - N)/2, you correctly assessed the asymptotic time complexity of your example as O(N^2).

Upvotes: 2

user16830227
user16830227

Reputation: 76

It occurs when either the outer or inner loop is bounded by a fixed limit (constant value) on iterations. It happens a lot in many problems, like bit manipulation. An example like this:

for (int i = 0; i < n; i++) {
    int x = ...;      //some constant time operations to determine int x
    for (int j = 0; x != 0; j++) {
        x >>>= 1;
    }
}

The inner loop is limited by the number of bits for int. For Java, it is 32, so the inner loop is strictly limited by 32 iterations and is constant time. The complexity is linear time or O(n).

Upvotes: 3

Related Questions