CODEWITHSUNDEEP
javafor-looptime-complexitybig-o
bigoh392e
bigoh392e

Reputation: 23

Time complexity of nested for loops where inner loop depends on outer loop

I have a nested for loop:

for(i = 0; i < n*n; i++)
   for(j = 0; j <= i/5; j++)
      print("Hello World!");

How do I find the time complexity of this loop.

I was thinking for the outer loop, it runs from 0 to n^2 (exclusive), so it runs n^2 + 1 times.

For the inner loop, it depends on i and this is where I get lost. Any pointers?

Upvotes: 2

Views: 1209

Answers (1)

rzwitserloot
rzwitserloot

Reputation: 103707

Almost always you can just plug in numbers that common sense tells you comprise the worst case scenario. Unless said worst case is guaranteed to only run a fixed amount of times regardless of N (i.e. all loops are near-optimal, except for at most 5 loops which aren't, even if we loop a thousand times - very rare) - then just do the math with the worst case.

This goes as far as each individual loop: Take the worst case for each. This is right, unless there is a link between the loops, e.g. if the inner loop runs 'worst case' only if some outer loop is guaranteed to run best case, and vice versa - when there is a clear relationship.

So, let's apply it here:

  • i runs from 0 to n*n, that part is easy.
  • j runs from 0 to i (we can ignore constant factors, so that /5 part is irrelevant, and we can forget about it).

The j loop's worst case is that i is equal to n*n, which makes j run from 0 to n*n. So let's just use that.

This is in fact the right answer; this is a loop that runs for n*n iterations (This is the j loop), and this process is repeated n*n times (The i loop), for a total complexity of O(n^4) (ouch, that's gonna fall over pretty quickly as n grows).

If you are unsure if the math works out, try to find linearity. That guarantees it. In this case, the best case scenario is when i is 0, in which case the j loop runs only once, vs. the worst case where the j loop runs n*n times. Crucially, the characteristic of the j loop is linear: Just chart out what happens to the performance of the j loop over the 'lifetime' of the i loop, and it's a simple straight relationship. First 5 j loops run once, second 5 j loops run twice, all the way up to the last j loop which runs n*n/5 times.

The 'average' of all j loops is this simply the middle of that line: half of n*n/5. Which is n*n/10, and constant factors do not matter, so that's still n*n. Hence why this is O(n^4), the same as for (j = 0; j < n*n; j++) would have been.

Upvotes: 2

Related Questions