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)+nT(n)=T(n/2)+n
B) T(n)=T(n/2)+O(1)T(n)=T(n/2)+O(1)
C) T(n)=T(n−1)+O(1)T(n)=T(n−1)+O(1)
D) T(n)=T(n−1)+nT(n)=T(n−1)+n
