183 views

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");
}
}
}
}
| 183 views
0
best case it will be $\Omega \left ( n \right )$

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

Ans given?
0
Best case  Ω(n)

Worst case O(n*n)
0

I think worst will be $O(n\sqrt{n})$

0
Best case - when n is prime number.
In that case printf() will run  $n+n-1=2n-1 \; times$
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

@ankitgupta.1729

@Shaik

Can u help here

what will be accurate?

+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
+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
Ohh.. My fault..
Yes it should be n+n-2+n=$\Omega (n)$
+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.
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. :(