CODEWITHSUNDEEP
time-complexity
Jane Foster
Jane Foster

Reputation: 471

Time complexity for nested loops

Here is a nested for loop. I work out the time complexity for it is nlg(n).

 int sum = 0;
 for(int k = 1; k < n; k*=2){
     for(int i = 1; i < n; i++){
            sum++;
     }
 }

My thoughts are as follows.

  1. The outer for loop: k will take values of 1, 2, 4, 8, ... Thus it will take lg(n) iteration.
  2. The inner for loop: i will take n iteration.

Hence, the overall operations taken will be nlg(n).

Am I right?

Upvotes: 0

Views: 148

Answers (1)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Yes, the order of growth you suggested is correct. You can show it like the following:

enter image description here

Upvotes: 0

Related Questions