I am not able to calculate the time complexity of this program.
`const int n=1e6+5;
int prime[n];
void pre()
{
prime[1]=1;
for(int i=2;i<n;i++)
{
if(!prime[i])
{
for(int j=2;i*j<n;j++)
{
prime[i*j]=1;
}
}
}
}`
can you tell what is the time complexity of this program in terms of big O notation
The inner loop iterates a number of times proportional to n/i for each iteration of the outer loop. So, the total number of iterations is something like n/2 + n/3 + … + n/n. We can factor out the n to get n * (1/2 + 1/3 + … + 1/n). We recognize the thing in parentheses is basically the harmonic series up to term n and the partial sums of the harmonic series have logarithmic asymptotic growth in n (see Wikipedia here).
So, it looks like the total number of iterations of the inner loop increases like n * log(n). Each iteration of the inner loop does constant work and outside the inner loop does constant work per iteration of the outer loop. Thus, we get a total amount of work like a * n + b * n * log(n) which is O(n log n).
Now this is probably a little sloppy since it's not technically a "free" operation to multiply two numbers. If we ignore this and assume we're talking about realistic computers where all multiplications take about the same time regardless of size (fixed-size variables) then this is fine. Really, if doing this by hand, you'd probably need to consider the cost of multiplying, which is probably proportional to the logarithm of the size of the numbers. This might add an extra logarithmic term giving something like O(n log^2 n) or something. YMMV.
Step by step mathematical formula:
