Asymptotic code fragment analysis

Question

I need to find a great run time O for the following snippet:

sum =0; for (int i=1; i<n; i++) { for (int j=1; j< n/i; j++) { sum = sum +j; } } 

I know that the outer loop is O (n), but I have a problem with analyzing the inner loop. I think this is O (log n).

Answer 1

Let me just write this in this pseudo-mathematical style.

 sum i <- [1..n] (sum j <- [1..n/i] 1) 

The inner loop (amount) needs

 n / i 

what does the whole member do

 sum i <- [1..n] (n/i) 

Simplify the amount in accordance with the law of distribution:

 n * (sum i <- [1..n] (1/i)) 

The intrinsic sum is in many ways similar to the integral over 1/x , which is logarithmic.

So O(n log n) right.

Answer 2

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 will work at least n times. Therefore, it must be at least O (n).

How many times does the inner loop have to run for each i? Does it increase, remains unchanged, or decreases as i increases?

It is clear that the number of steps in the inner loop will decrease as i increases, and more importantly, it decreases nonlinearly. So you know that this is not as bad as O (n ^ 2).

So it's somewhere between O (n) and O (n ^ 2) .... a little more analysis on how steps decreasing in the inner loop should get you there. EDIT: ... Although it seems like people already gave it away :)

Answer 3

As Dave said, this is O (n log n), because the inner loop is O (log n).