# Problem

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

```
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

##### The Complete Spring Boot Development Bootcamp – Become a Java Web Developer

Feedback Summary

0.0

0 students

5

0%

4

0%

3

0%

2

0%

1

0%

Written Reviews

There are no written reviews yet.