I need to state the big o of the following fragment:
sum =0;
for (int i=1; i<n; i++) {
for (int j=1; j< n/i; j++) {
sum = sum +j;
}
}
I know the outer loop is O(n) but I am having a problem analyzing the inner loop. I think it's O(log n). I would appreciate any help. Thank you in advance.
As Dave said, it's O(n log n) because the inner loop is O(log n).
Let's just write this in this pseudo-mathematical style.
sum i <- [1..n] (sum j <- [1..n/i] 1)
The inner loop (sum) needs
n / i
iterations, which makes the whole term
sum i <- [1..n] (n/i)
Simplify the sum according to the distributive law:
n * (sum i <- [1..n] (1/i))
The inner sum is largely similar to the integral over 1/x, which is logarithmic.
So O(n log n) is right.
The best approach to this is to consider how many steps the algorithm will take.
If you have n elements, you know that the outer loop is going to run at least n times. So it has to be at least O(n).
How many times does the inner loop have to run for each i? Does it increase, stay the same or decrease as i increases?
It's clear that the number of steps in the inner loop will decrease as i increases, and more importantly, it decreases non-linearly. So you know it isn't as bad as O(n^2).
So it's somewhere between O(n) and O(n^2).... a bit more analysis on how the steps decrease in the inner loop should get you there. EDIT: ... Although it looks like people already gave it away :)