What's the bigO of stacked loops?

Question

When you have a function that has multiple non-nested loops, does that change the time complexity from O(N)? I know that if you were to write a function that logs every element of an array, you could do this with a single loop, giving you a bigO of O(N), but if you added more loops, would that give you a bigO of O(N * number of loops)?

Consider this string compression function, what is it's bigO given that it loops over the string multiple times:

 function compression(string) {
  let compressed = "";
  let map = {

  }

  string.split("").forEach((e, i) => {
    map[e] = 0;
  })

  string.split("").forEach((e, i) => {
    map[e] += 1;
  })

  for (var element in map) {
    compressed += element + map[element];
  }
  if (compressed.length > string.length) {
    return string;
  } else {
    return compressed;
  }
}

Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Prune, Dec 05 '18 at 22:36

score 1 · Answer 1 · answered Dec 05 '18 at 22:26

1

In regards to non-nested loops like the ones you have shown, the time complexity remains O(N). This is because the number of loops is a constant - for example, if you run through N elements 3 times, in big O notation you can drop the constant. Therefore, it's still O(N).

Note: This assumes the number of loops is a constant. If the number of loops depends on the number of elements in any way, then you will need to take that relationship into account.

answered Dec 05 '18 at 22:26

Andrew Fan

1,313
5
17
29

Thank you for this, do you have any insight as to why we drop constants? Is it because bigO is a description of how the algorithm performs as N grows rather than a description of how many executions or how long the algorithm takes? – WriterState Dec 05 '18 at 22:34
1

@WriterState: we drop the constant because the complexity estimate has no unit. It is neither in milliseconds, nor in years, nor in instructions, nor in anything, and we don't want to know, because this is completely architecture dependent. – Dec 05 '18 at 23:58

score 0 · Answer 2 · answered Dec 06 '18 at 11:17

By definition, an algorithm is O(N) when the number f(N) of elementary operations it needs to perform on an input of size N satisfies:

f(N) <= C.N    ; N >= N0

for some positive constant C, independent from N, where N0 is some initial index, also independent from N.

Say you combine three loops, each of them O(N). According to the definition you will have three pairs of constants (C1, N1), (C2, N2) and (C3, N3) such that

loop1(N) <= C1.N  ; N >= N1
loop2(N) <= C2.N  ; N >= N2
loop3(N) <= C3.N  ; N >= N3

Then,

loop1(N) + loop2(N) + loop3(N) <= (C1 + C2 + C3)N       ; N >= max(N1,N2,N3)

and the definition of O(N) holds for the constant C = C1+C2+C3 and the initial index N0 = max(N1,N2,N3). Hence, the concatenation of a constant number of O(N) algorithms is again O(N) because the constants C and N0 do not depend on N.

What's the bigO of stacked loops?

2 Answers2