worst case $O(n\sqrt{n})$

Ans given?

The Gateway to Computer Science Excellence

0 votes

**What ****is**** the best case and worst case of the algorithm? And when will best case and worst case will happen??**

int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j<=n ; j++) { printf("Hello"); } } } }

0

@srestha how are you getting root n factor?

I don't know if I am correct, but how I analyzed is if we take n sufficiently big, there will be many factors of that number which will be contributing to the execution of inner for loop. So asymptotically it should increase at a rate of n^2.

+1

mam, I don't think we can find it accurately. In worst case , we have to find the no. of factors for a particular 'n' and for this , we have to do prime factorization which is a difficult task for a large 'n'...

@Verma Ashish, can you please explain how are you getting "-1" in n+n-1 ?

0

For i=1 inner loop will run $n\; times$. (j=1 to n)

Now for $i=2\; to\; n$ outer loop runs $\color{blue}{(n-1)\; times}$.. since comparison is unsuccessful so inner loop will not execute.(for prime n)... That's why i added n-1

Now for $i=2\; to\; n$ outer loop runs $\color{blue}{(n-1)\; times}$.. since comparison is unsuccessful so inner loop will not execute.(for prime n)... That's why i added n-1

+1

in case of prime numbers, for i=1 and i=n , inner loop will be executed... So, should not it be n+n+(n-2)*O(1) ?

+1

I think -

Best case is when n is prime, so complexity will be only of $\Theta(n)$ since the outer loop will run only once, and inner loop will run at i=1 and i=n right?

Worst case will be when n is divisible by every single number between 1 and n, in that case the outer loop runs only once and inner loop runs n times. I don't think we need to know if such number exists. Let's assume it does in worst case, so in worst case the complexity will be $O(n^2)$.

As a side question, is there a reason to use $\Omega(n)$ instead of $O(n)$ for best case?

Correct me if I'm wrong.

Best case is when n is prime, so complexity will be only of $\Theta(n)$ since the outer loop will run only once, and inner loop will run at i=1 and i=n right?

Worst case will be when n is divisible by every single number between 1 and n, in that case the outer loop runs only once and inner loop runs n times. I don't think we need to know if such number exists. Let's assume it does in worst case, so in worst case the complexity will be $O(n^2)$.

As a side question, is there a reason to use $\Omega(n)$ instead of $O(n)$ for best case?

Correct me if I'm wrong.

0

@toxicdesire why we don't need to know about a number which can be divided by any number b/w 1 to n to analyse the time complexity accurately here. There is a property called "correctness" associated with every algorithm. So, we need to prove whether such number exist or not to analyse TC accurately. check here. I think, O($n^2$) is correct but we can't analyze TC accurately here in worst case.I am not sure whether O(n) is correct or not.I guess $\Omega$ is associated with a problem like sorting can't be done better than $\Omega(nlogn)$ means It shows lower bound and it does not mean best case.So, I think it should be O(n) in best case here.

Please correct me if I am wrong.

+1

@ankitgupta.1729 yes you are right. Inner loop execution is dependent on the mod operation. So from 1 to n, we will have to find execution for each and then sum them up.

To find the factors of a given number we have to do prime factorization and then find it. Only for these values among n we will be getting n square.

So yes there is no direct way we can analyze this.

0

I think we don't need to know if such number exists or not to say the time complexity is $O(n^2)$. Of course, it is not a tightest bound, and it's not incorrect either. I concluded it because of the two loops, and worst that can happen in this particular case is (ignoring all the number theory) , inner loop runs for every iteration of outer loop.

Let's try and get a tighter bound.

We know, that a number can have at most $2 \cdot \sqrt{n}$, since the divisors will be in pairs of $\left( x, \frac{n}{x} \right)$, and the highest value of $x$ will be $\sqrt{n}$ when $n$ is a perfect square. Hence, it is safe to say that worst case complexity is $O(n \cdot \sqrt{n})$.

Can we get a tighter bound than $O(n \cdot \sqrt{n})$?

I think so, yeah. It will be $n \cdot n^{O( \frac{1}{\log \log n})}$, if $n$ is large. If you're interested, here's link to the proof.

Can we get tighter than this? I don't know. I am not a mathematician. Let me know if you know. :(

52,375 questions

60,610 answers

202,044 comments

95,428 users