"how to solve big-o notation for prime number function?" Code Answer

@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:

the first sum is up to sqrt(i) since this is the point where j > (i / j).
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.
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)