TIme Complexity Algo

Question

for(i=1 to n)
    {
        if(n mod i==0)
        {
            for(int j=1 to n)
            printf(j);
        }
    }

Comments

$O(n^2)$

---

Please explain.

---

srestha now check the answer .!

Answer 1

$T(n) = \Omega(n)$, when $n$ is a prime number.

$T(n) = O\left(n\sqrt n \right)$, when $\sqrt n$ is a factorial.

Comments

sir for 120 i got 16 different divisor which makes the mod value true and hence the printf will run .16* 120 = 1920 . i think i am ryt but sir wt about the time that u got as O(n²) can u give me hint to think further more about this thanks .

---

@Kunal I was wrong. Corrected the answer now.

---

sir here n =120  but not √n=120  am i rt ?

Answer 2

The nested loop runs only in case of divisor of N, whenever i dividies N , the nested loop runs N times,

As divisor of any number are not equivalent to N , they may be less then sqrt(N)

And to find number of divisors of any number, it will take sqrt(N) complexity.

So overall lets say N have sqrt(N) divisors

Hence as per my knowledge , the overall complexity, of the above code is sqrt(N) * N

Not N^2.

Best complexity is o(N)  in case of primes number, when N = prime , it have only two divisors in that case complexity is linear.