Search code examples
javatime-complexityspace-complexity

What is the time and space complexity of this code? I'm very confused on this subject so I am asking


This is my code, it is a russian peasant multiplication algorithm. I find the time and space complexity very confusing so I needed some help.

This is also for java language

Thank you.

int num1 = Integer.parseInt(jTextField1.getText());
int num2 = Integer.parseInt(jTextField2.getText());


int res=0;

 // While second number doesn't become 1

    while (num2 > 0)

    {

         // If second number becomes odd, 

         // add the first number to result

         if ((num2 & 1) != 0)

             res = res + num1;



        // Double the first number 

        // and halve the second number

        num1 = num1 << 1;

        num2 = num2 >> 1;

    }

   jTextField3.setText(String.valueOf(res));
}

Solution

  • The loop continues to execute provided that num2 be greater than zero. After each iteration of the loop, num2 is halved. This means that the loop will execute log_2(num2) times. So, assuming num2 be represented by N, we can say that the complexity of this loop is log_2(N).