A well-known problem is, given a prime number P, find the next smallest prime number. An algorithm to solve this is to go to P+1, check if it's prime by checking the divisibility of all numbers from 2 up to floor(sqrt(P+1)) (Because all prime divisors of a number will be smaller or equal to it's square root), then check the same for P+2, P+3 and so on, until a prime number is found. Prove that the complexity of this algorithm is O(P).

Solution:

According to Andrica's conjecture , for two prime numbers p and q with p < q and no other prime between them (q is the next smallest prime after p), sqrt(q) — sqrt(p) < 1 which becomes q < p + 2\sqrt(p) + 1 and since they are natural numbers, q <= p + 2*sqrt(p). Therefore, the gap between p and q is at most 2*sqrt(p).

This means that our algorithm will check at most 2*sqrt(p) numbers (or to be more precise, floor(2*sqrt(p)) ). For each number we will check up to its square root, therefore we will do floor(sqrt(p+1)) + floor(sqrt(p+2)) + floor(sqrt(p+3)) + ... + floor(sqrt(p + 2*floor(sqrt(p)))) operations in total. But all the elements are < floor(sqrt(p + p)) = floor(sqrt(2*p)). There are floor(sqrt(2*p)) elements, so the total number of operations is less than floor(sqrt(2*p))*floor(sqrt(2\p)) <= 2*p. Thus this algorithm will do up to 2*P operations and the complexity will be O(P).