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

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