4
for(int i = 0; i < n; i++) {
   for(int j = 0; j < i; j++) { 
      O(1);
   }
}

here the func is n * (n+1) / 2 but what if the outerloop condition is i < log(n)? I have problems with loops that relates on each other.

Dmitry Bychenko
  • 165,109
  • 17
  • 150
  • 199
Charlie
  • 1,169
  • 2
  • 16
  • 30
  • If you replace `n` with something else, just replace every `n` in `n * (n+1) / 2` with the same thing. This seems to come down to a lack of understanding of basic algebra (or a temporary mental lapse). – Bernhard Barker Jun 21 '17 at 15:48

3 Answers3

3

You just have to count the total number of iterations:

1 + 2 + 3 + .. + n - 1 = n * (n - 1) / 2

as you correctly inferred. When you replace n with log(n), just do the same in the final formula, which then becomes log(n) * (log(n)+1) / 2, or in Big-O notation, O((log(n))^2).

Miljen Mikic
  • 14,149
  • 6
  • 55
  • 63
2

If the condition of the outer loop is changed to i < log(n) then the overall complexity of the nested two-loop construct changes from O(n2) to O(log(n)2)

You can show this with a simple substitution k = log(n), because the complexity of the loop in terms of k is O(k2). Reversing the substitution yields O(log(n)2).

Sergey Kalinichenko
  • 697,062
  • 78
  • 1,055
  • 1,465
0

For nested for loops (when using the O notation, ofc) you can multiply the worst-case scenario of all of them. If the first loop goes to x and you have a nested loop going to i (i being at worst-case x) then you have a run-time complexity of O(x^2)

Dinu Sorin
  • 215
  • 2
  • 6