Time Complexity

Question

//n is a prime number here

int main()
{
    for(i=1;i<=n;i=2*i)
       {
             for(j=1;j<=n;j++)
               {
                 if(n%i==0)
                   {
                        k=1;
                      while(k<=n)
                        {
                       a=b+c;
                       k=k+1;
                        }
                   }
               }
         }
}

Comments

sir i think answer should b O(nlogn)

because first for loop run lgn(n) times

for second for loop j=1          while loop n times

                            j=2             1 time  because n%2==0 is false

                            j=3          1 time  because n%2==0 is false so.............

                           j=n            n times n%n==0 true

so total second loop=n+1+1+1.............+n=n-2+2n

and first loop log(n) times so O((3n-2)log(n))=O(nlog(n))

---

@Hemant Parihar ,when i =n then it will run n^2 .

---

@rahul

n is a prime number here. And i is getting double in each iteration. It never divide n properly when n > 2.