What is the growth function and order in this code?

Question

I'm trying to understand the growth function of this code.

 for (int count=0; count < n; count++) {
   for (int count2=1; count2 < n; count2=count2*2) {
     System.out.println(count + ", " + count2);
   }
 }

Answer 1

The outer loop is linear since you're incrementing by one each time. The inner loop is log(n) since your upper bound would have to increase exponentially to keep up with the growth of the count2 variable therefore the entire nested iteration is nlog(n) .