What will be the time complexity of the following code which raises an integer x to the power y?
Posted: Wed Jul 13, 2022 7:40 pm
#include<stdio.h>
int power(int x, int y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)*power(x, y/2);
else
return x*power(x, y/2)*power(x, y/2);
}
int main()
{
int x = 2;
int y = 3;
printf("%d", power(x, y));
return 0;
}
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)
int power(int x, int y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)*power(x, y/2);
else
return x*power(x, y/2)*power(x, y/2);
}
int main()
{
int x = 2;
int y = 3;
printf("%d", power(x, y));
return 0;
}
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)