#time-complexity#daa

Question

What will be time complexity for the following algo where  n is a Prime number?

main()

{

for(i=1; i<=n; i=2*i)

   for(j=1; j<=n; j++)

    {

     if(n%i == 0)

         while(k<=n)

              { a=b+c

               k=k+1

              }

    }

}

Comments

please correct the question !what is k? what is its initial value ?

Answer 1

outer loop runs floor(logn +1) = log n and inner loop worst case n^2 so worst case total time complexity of program=(n^2)logn,plz correct me if wrong

Comments

ok i got it! yes it is the correct answer