What will be the recurrence relation of the following code?
int xpowy(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if ((n % 2) == 0) return xpowy(x * x, n / 2);
else return xpowy(x * x, n / 2) * x;
}
a) T(n) = T(n/2) + O(1)
b) T(n) = T(n/2) + O(n)
c) T(n) = T(n/2) + O(log n)
d) T(n) = T(n/2) + O(n²)