# Problem

This function uses recursion to compute the power of a number. What is the time complexity?

```python
def power(x, n):
    # Base case
    if n == 0:
        return 1
    if n == 1:
        return x
    # Recursive case
    if n % 2 == 0:
        return power(x, n/2) ** 2
    else:
        return x * power(x, n-1)
```

# Solution

The function repeatedly divides the input by 2 until the base case is reached. We expect the runtime to be logarithmic w.r.t. the input size.


-----
##### This workbook was created by Jad and Rayan Slim. Feel free to explore some of their courses:
##### [The Complete Java Development Bootcamp](https://udemy-redirect-app.herokuapp.com/java)
##### [The Complete Spring Boot Development Bootcamp – Become a Java Web Developer](https://udemy-redirect-app.herokuapp.com/spring)


Problem 10 Solution

Problem 12 Solution

Problem 4 Solution

Problem 8 Solution

Workbook

Problem 7 Solution

Problem 15 Solution

Problem 2 Solution

Problem 14 Solution

Problem 6 Solution

Problem 5 Solution

Problem 17 Solution

Problem 3 Solution

Problem 1 Solution

Problem 16 Solution

Problem 13 Solution

Problem 11 Solution

Problem 9 Solution

Big O