time complexity

Question

for(i=1;i<=n;++i)
{
j=1;
while(j<=n)
j=2*j;
for(k=1;k<=n;++k)
c=c+1;
}
then what is the time complexity will be?

Comments

O(n^2).  ?

---

Yes it will be O(n²).

As n*(logn + n) =O(n²).

---

Outer loop will run for n times,

While loop will run for logn  times

And inner for loop will run for n times

So time complexity will be  n(n+logon)

Which is n^2 + nlogn

Here leading term is n^2

So complexity will be O(n^2)

Answer 1

For each iteration of the outer loop ,

the inner j loop runs for Log(n) time , and k loop runs for n time.

And outer loop runs for n times.

So complexity will be , n(Log(n)+n) = nLog(n) + n^2

Asymptotically nLog(n) + n^2  = O(n^2)

Comments

i think you are right