Algorithm to Calculate The Power Of n^x

Q: Write an Algorithm to calculate the power of a number. Input will be n and x, and your algorithm should output the value of n^x.

base = input('Enter the base (n): ')
expo = input('Enter the exponent (x): ')

// expo = exponent (x)

float power(int base,  int expo) { 
    if (expo is 0) 
        return 1
    sid = power(base, expo/2)
    if (expo % 2 == 0)
       return sid * sid
    else{
       if(expo > 0)
           return sid * sid * base
       else 
           return sid * sid / base
    }
}

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(log n)

Because of “recursive stack space“