Algorithm Time Complexity-Self Doubt

Question

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");
         }
      }
  }
}

Comments

best case it will be $\Omega \left ( n \right )$

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

Ans given?

---

Best case  Ω(n)

Worst case O(n*n)

---

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

Ref:https://gateoverflow.in/1249/gate2007-51?show=164432

---

Best case - when n is prime number.
In that case printf() will run  $n+n-1=2n-1 \; times$

---

@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.

---

@ankitgupta.1729

@Shaik

Can u help here

what will be accurate?

---

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 ?

---

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

---

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) ?

---

Ohh.. My fault..
Yes it should be n+n-2+n=$\Omega (n)$

---

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.

---

@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.

---

@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.

---

@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. :(

Answer 1

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)

Comments

 

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).