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));
}
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)
.