1 votes 1 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"); } } } } Algorithms algorithms time-complexity self-doubt + – sumitr asked Apr 10, 2019 sumitr 1.3k views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply srestha commented Apr 10, 2019 reply Follow Share best case it will be $\Omega \left ( n \right )$ worst case $O(n\sqrt{n})$ Ans given? 0 votes 0 votes sumitr commented Apr 10, 2019 reply Follow Share Best case Ω(n) Worst case O(n*n) 0 votes 0 votes srestha commented Apr 10, 2019 reply Follow Share I think worst will be $O(n\sqrt{n})$ Ref:https://gateoverflow.in/1249/gate2007-51?show=164432 0 votes 0 votes Verma Ashish commented Apr 10, 2019 reply Follow Share Best case - when n is prime number. In that case printf() will run $n+n-1=2n-1 \; times$ 0 votes 0 votes tusharp commented Apr 11, 2019 reply Follow Share @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. 0 votes 0 votes srestha commented Apr 11, 2019 reply Follow Share @ankitgupta.1729 @Shaik Can u help here what will be accurate? 1 votes 1 votes ankitgupta.1729 commented Apr 11, 2019 reply Follow Share 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 ? 1 votes 1 votes Verma Ashish commented Apr 11, 2019 reply Follow Share 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 0 votes 0 votes ankitgupta.1729 commented Apr 12, 2019 reply Follow Share 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 votes 1 votes Verma Ashish commented Apr 12, 2019 reply Follow Share Ohh.. My fault.. Yes it should be n+n-2+n=$\Omega (n)$ 1 votes 1 votes toxicdesire commented Apr 12, 2019 reply Follow Share 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. 1 votes 1 votes ankitgupta.1729 commented Apr 12, 2019 reply Follow Share @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. 0 votes 0 votes tusharp commented Apr 12, 2019 reply Follow Share @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. 1 votes 1 votes toxicdesire commented May 8, 2019 reply Follow Share @ankitgupta.1729 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. :( 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Firstly its not mentioned in the question if “n” is even or odd. So assuming in best case its only divisible by 1 and then time complexity becomes Ω(n) but in worst case “n” is divisible by all numbers making the worse case time as O(n^2) rish1602 answered Jun 16, 2021 rish1602 comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Aug 12, 2021 reply Follow Share Firstly its not mentioned in the question if “n” is even or odd. So assuming in best case its only divisible by 1 See every number is divisible by 1 and itself, Your statement is wrong. Now the algorithm will give us the best case time complexity for input having minimum divisors means prime numbers will give us the best case time complexity O(n) (exact value 3n-2). 0 votes 0 votes Please log in or register to add a comment.