CODEWITHSUNDEEP
c#time-complexitybig-o
ip31
ip31

Reputation: 1

What is the time complexity for the below code snippet?

Below is a code snippet which contains nested for loop. Technically it should be 

O(variableFour*variableFour),

but that not the case.

void main() { 
   int variableOne, variableTwo, variableThree = 0;
   int variableFour = 10;

   for (variableOne = variableFour / 2; variableOne <= variableFour; variableOne++) {
      for (variableTwo = 2; variableTwo <= variableFour; variableTwo =variableTwo * 2) {
         variableThree = variableThree + variableFour / 2;
      }
   }
}

Upvotes: 0

Views: 69

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186688

It's not O(variableFour * variableFour) == O(variableFour**2). Look at the inner loop:

 for (variableTwo = 2; variableTwo <= variableFour; variableTwo = variableTwo * 2)

Note that that we multiply, not add: variableTwo = variableTwo * 2 so we loop over

 variableTwo = 2, 4, 8, 16, ..., 2**i, ..., variableFour

So the inner loop complexity is O(log(variableFour)) and combined complexity (for both inner and outer loops) is

 O(variableFour * log(variableFour))

Upvotes: 1

Related Questions