0
Follow
0
View

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

razuvious 注册会员
2023-01-25 14:41

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.

cxs_2011 注册会员

Publish Time
2023-01-25 14:41
Update Time
2023-01-25 14:41