How to solve Big-O Notation for prime number function?

Question

I am trying to understand Big-O Notation. So sorry if I am asking something that is too obvious but I can't seem to wrap my head around this.

I have the following C# code function that I am trying to calculate Big-O Notation for.

for (i = 2; i < 100; i++)
     {
        for (j = 2; j <= (i / j); j++)
           if ((i % j) == 0) break; // if factor found, not prime
        if (j > (i / j)) 
           Console.WriteLine("{0} is prime", i);
     }

Now what I got so far is that I think that both the if clauses are considered constant O(1) and not taken into account for the calculation of this algorithm? And also if I have understood correctly a single for loop

for(i = 0; i < 100; i++)

since it is a linear function would be O(n) and a nested loop that does not depend on a variable from the surrounding loop

for(i = 0; i < 100; i++)
    for(j = 0; j < 100; j++)

Is O(n^2)? But how do I calculate a function such as the top one where the second loop is dependent on the first loop and creates a non-linear function?

I found a definition for linearithmic that says

Linearithmic algorithm scales to huge problems. Whenever N doubles, the running time more (but not much more) than doubles.

While this seems to be a good description of how this code snippet runs would that mean that it is O(N Log[n]) and if so how could I calculate this?

Answer 1

@Jon is close but his analysis is a bit wrong, and the real complexity of your algorithm is O(n*sqrt(n)).

This is based on the fact that for each number i, the expected number of 'work' you should do in the inner loop is:

1/2 + 2/3 + 3/4 + ... + (sqrt(i)-1)/sqrt(i) = 
 = 1-1/2 + 1-1/3 + ... + 1-1/sqrt(i)
 = sqrt(i) - (1/2 + 1/3 + ... + 1/sqrt(i)
 = sqrt(i) - H_sqrt(i)

since H_sqrt(i) (The harmonic number) is in O(log(sqrt(i)) = O(1/2*log(i), we can conclude that the complexity is O(sqrt(i)-log(i)) = O(sqrt(i)), per prime number calculation.

Since this is done repeatedly per each i, the total complexity of the problem is O(sqrt(2) + sqrt(3) + ... + sqrt(n)). According to this forum thread, the sum of squared roots is in O(n*sqrt(n)), which is "worse" than O(nlogn).

Things to notice:

1. The first sum is up to sqrt(i) since this is the point where j > (i / j).
2. The first sum is (j-1)/j for each j, because on average one out of j elements is getting into the break (1/3 of the elements are dividable by 3, 1/4 by 4,...) this leaves us (j-1)/j that are not - and this is the expected work we have.
3. The equality O(log(sqrt(n)) = O(1/2*log(n) comes from O(log(n^k))=O(k*log(n))=O(log(n)) for any constant k. (in your case k=1/2)

Answer 2

Analyzing your algorithm, I came up with the following:

• The inner loop doesn't iterate when i is in the interval [2, 3].
• The inner loop does iterate once when i is in the interval [4, 8].
• The inner loop does iterate twice when i is in the interval [9, 15].
• The inner loop does iterate three times when i is in the interval [16, 24].
• The inner loop does iterate four times when i is in the interval [25, 35].
• The inner loop does iterate five times when i is in the interval [36, 48].
• The inner loop does iterate six times when i is in the interval [49, 63].
• The inner loop does iterate seven times when i is in the interval [64, 80].
• The inner loop does iterate eight times when i is in the interval [81, 99]. I had to go to a range broader than 100 to verify the above.
• The inner loop does iterate nine times when i is in the interval [100, 120].

The intervals, which depend on i's value, can be represented like this:

[i^2, i * (i + 2)]

Therefore, we can do this:

An empiric verification:

With a useful WolframAlpha link:

http://www.wolframalpha.com/input/?i=sum[+floor%28+i^%281%2F2%29%29+-+1+]+with+i+from+2+to+99.

Formally, we can state the following:

Answer 3

I looked at your code - and there is no n. The code isn't dependent on any n. It will always run in exactly the same fixed time. You can calculate how long it takes, but it's always the same, constant, time. As written, your code starting with "for (i = 2; i < 100; ++i)" runs in O (1).

So change the first line to

for (i = 2; i < n; ++i)

and now we have code that actually depends on n. The inner loop runs at most sqrt (i) iterations, which is less than sqrt (n). The outer loop runs about n iterations. So the execution time is at most O (n sqrt (n)) = O (n^1.5).

In reality, it will run faster. It doesn't usually run up to sqrt (i), but only until it finds a divisor of i. Half the numbers are divisible by 2 (one iteration). One third of the rest is divisible by 3 (two iterations). One fifth of the rest is divisible by 5 (four iterations). About n / ln n numbers are primes with sqrt (n) iterations. About n / ln n more numbers are the product of two primes > n^(1/3) with up to sqrt (n) iterations. The rest has less than n^(1/3) iterations.

So the code actually runs in O (n^1.5 / ln n). You code improve this by using a table of the primes up to sqrt (n), and you would be down to O (n^1.5 / ln^2 n).

But in practice, you can bet that Console.WriteLine () will take an awful lot longer than checking that a number is prime. If you insist on listing all primes, your algorithm will be dominated by the O (n / ln n) time with an awfully big constant factor for displaying the results until n gets really big.