Menu
I'm new to Java, my question is on big-O complexity.
For a), it is clearly O(n^2) for a nested loop.
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
however, for b), with sum++ operation at the end, and complications in the nested loop, does that change the its Big-O complexity at all?
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
783
O(log n) - Logarithmic Complexity The time taken increases with the size of the data set, but not proportionately so. This means the algorithm takes longer per item on smaller datasets relative to larger ones. 1 item takes 1 second, 10 items takes 2 seconds, 100 items takes 3 seconds.
Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound) Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound) Finally, Big Θ describes the set of all algorithms that run at a certain speed (it's like equality)
Here, i: It is a loop variable. n: Number of times the loop is to be executed. In above scenario, loop is executed 'n' times. Therefore, time complexity of this loop is O(n).
In your second example, the first for iterate n times, and the second iterate log2(n) times, since you divide j by 2 in each iteration. Therefore, the complexity is O(n log2 n).
sum++ in the last line does not affect the complexity.
154
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
