Write recurrence formulas for the time complexity of the following functions, that all should compute x^n for n 0. Then find the order of magnitude for each time complexity. Consider: Are all the functions strongly correct. Are they all certain to return some value? Note that if a function goes into infinite recursion or an infinite loop then it is natural to say that the time complexity is infinite, i.e. O()

1. public static double pow (double x , int n) { if ( n==0 ) return 1.0; if ( n%2==0 ) return pow(x*x, n/2); else return x*pow(x*x, n/2); }

2. public static double pow(double x , int n) { if ( n==0 ) return 1.0; return x*pow(x, n1); }

3. public static double pow( double x , int n) { if ( n==0 ) return 1.0; if ( n%2==0 ) return pow (x, n / 2) * pow(x, n / 2); else return x*pow(x, n / 2) * pow(x, n / 2) ; }

4. public static double pow(double x , int n) { if ( n==0 ) return 1.0; if ( n%2==0 ) return pow(pow(x, n / 2), 2); else return x*pow (pow(x, n / 2), 2); }