In the first approach, you testing divisibility with each number from 1 to
sqrt(x), so the complexity of testing a single number is
sqrt(x). According to this formula, the sum of first
n roots can be approximated to
Time complexity of method 1:
O(N*sqrt(N)) (N is the total count of numbers being tested).
In the second approach, there are 2 cases:
- If a number isn’t prime, all primes upto
nare tested. Complexity –
O(n/6) = O(n)
- If a number is prime, we can approximate the complexity to be
O(log(n))(there might be a more accurate calculation of the complexity for this case, I’m making an approximation since this wouldn’t matter in the proof)
For the prime numbers, using the fact that we test them with
(n/6) primes, the complexity would become
5/6 + 7/6 + 11/6 + 13/6 + 17/6 ..... (last prime before n)/6. This can be reduced to
(sum of all prime numbers till n)/6 for the time being. Now, the sum of all prime numbers upto
N can be approximated as
N^2/(2*logN). Thus the complexity for this step becomes
N^2/(6*(2*logN)) = N^2/(12*lognN).
Time complexity of method 2:
O(N^2/(12*lognN)) (N is the total count of numbers being tested).
(if you want, you can make more accurate bounds for the time complexities of each step. I have made a few approximations since it helps in proving the point without making any overoptimistic assumption).
CLICK HERE to find out more related problems solutions.