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

5

@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)
By Nedko Dimitrov on July 23 2022