Analysis of algorithms

Question

When we have to use multiplication and addition  while finding the time complexity of an algorithm

Eg( n * logn )or (n + logn)

Please explain me this concept

Thanks

Comments

for (i=1;i<=n;i++){

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

count++;

}

The above is n*logn since the inside loop runs for logn times and outer loop runs for n times.

So for each of n times , inner loop runs log n times. Thus , nlog(n).

 

and if you take the inner loop outside.

for (i=1;i<=n;i++){

}

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

count++;

 

This is simply n + logn , since both the loops are running in a non-cascade manner

---

Thanks Prashant!

---

Welcome Mayank :)