CODEWITHSUNDEEP
javascriptalgorithmtime-complexitybig-o
WriterState
WriterState

Reputation: 369

What's the bigO of stacked loops?

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;
  }
}

Upvotes: 0

Views: 198

Answers (2)

Leandro Caniglia
Leandro Caniglia

Reputation: 14843

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.

Upvotes: 0

Andrew Fan
Andrew Fan

Reputation: 1321

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.

Upvotes: 1

Related Questions