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.
Join Stack Overflow to learn, share knowledge, and build your career.
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.
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)
.
1 + 2 + 3 + .. + n = n * (n+1) / 2
, not 1 + 2 + 3 + .. + n - 1
.
– Anthony Labarre
Jun 22 '17 at 8:27
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).
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)
n
with something else, just replace everyn
inn * (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