O notation of a Loop

Question

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.

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

Miljen Mikic · Accepted Answer · 2017-06-23T13:37:03.657

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).

edited Jun 23 '17 at 13:37

answered Jun 21 '17 at 14:50

Miljen Mikic

14,765
8
58
66

`1 + 2 + 3 + .. + n = n * (n+1) / 2`, not `1 + 2 + 3 + .. + n - 1`. – Anthony Labarre Jun 22 '17 at 08:27
@AnthonyLabarre Of course, very stupid mistake. Tnx. – Miljen Mikic Jun 23 '17 at 13:34

score 2 · Answer 2 · answered Jun 21 '17 at 14:50

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(n²) to O(log(n)²)

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

score 0 · Answer 3 · answered Jun 21 '17 at 15:18

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)

answered Jun 21 '17 at 15:18

Dinu Sorin

215
2
6

O notation of a Loop

3 Answers3