Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have explained the algorithm to Find Cube root using Binary Search along with Time and Space Complexity analysis.

Table of contents:

- Introduction
- Finding cube root using Binary Search
- Perfect Cube
- Cube root with precision

- Time and Space Complexity

Pre-requisites:

## Introduction

When someone needs to find the cube of a number, then they can just multiply that number by itself three times, and alas! They have the answer. But, when one needs to go in the other direction (finding cube-root), theirs no direct formula to find this number and, because of this it is required to search this number throughout the space of [1, N].

### A little stroll to Linear Search

If you desire, you can skip this and goto the solution

So, I was curious, why not Linear Search? I mean, it's âˆ›N. maybe a mathematician would know by one look which one is smaller or greater âˆ›N or `log`

._{2}N

Well in my case, I went and took the `log`

of a bunch of numbers and then compared them together and got the following output.

```
from math import ceil, log
for i in range(1, 30, 2):
print("{} - {} | {} - {}".format(
i,
ceil(log(i**3, 2)),
i+1,
ceil(log((i+1)**3, 2))
)
)
```

1 - 0 | 2 - 3 3 - 5 | 4 - 6 5 - 7 | 6 - 8 7 - 9 | 8 - 9 9 - 10 | 10 - 10 11 - 11 | 12 - 11 13 - 12 | 14 - 12 15 - 12 | 16 - 12 17 - 13 | 18 - 13 19 - 13 | 20 - 13 21 - 14 | 22 - 14 23 - 14 | 24 - 14 25 - 14 | 26 - 15 27 - 15 | 28 - 15 29 - 15 | 30 - 15

Conclusion:

As you go further, log starts to become smaller, therefore,

`log`

<_{2}N`âˆ›N`

. So, binary search would be better than Linear.

Well, back to the topic...

## Finding cube root using Binary Search

### Perfect Cube

If we have to find cube root for a perfect cube, then we can just apply binary search directly on the space of [1, N], and return `x`

where `x`

equals to `x`

.^{3}

This should look something like the following,

```
1 def perfect_cube_root(N):
2 start = 1
3 end = N
4 mid = (start + end) // 2
5
6 while mid != start and mid**3 != N:
7 if mid**3 > N:
8 end = mid
9 else:
10 start = mid
11 mid = (start + end) // 2
12 return mid
```

The `(mid != start) and`

condition, in the while loop, help to return a smaller value in case the loop doesn't find a perfect cube root. And without this condition, the loop will run infinitely.

So, for example,

If we do `perfect_cube_root(9)`

, since `9`

comes between two perfect cubes `8`

and `27`

because of this, the above loop will return `2`

, which is a cube-root of `8`

.

Why write this function this way?

Well, we're going to use this in the next `cube_root`

with precision function.

## Cube root with precision

Now to find decimal values of a cube root, we can first search for a smaller result using `perfect_cube_root(N)`

and, if it returns a perfect cube root, then return it or proceed to search for precision.

The idea here is to find a value in decimal which will be a perfect cube root or a nearest smaller value.

In other words, we will search between `.0`

and `.9`

, a perfect match or nearest smaller value, and then decrease the power in the case of `.0`

and `.9`

, another search will happen in-between `.00`

and `.09`

.

And while the above search happens, we should keep adding the found values to the result with increasing precision.

Code for the above idea should look like the following one:

```
1 def cube_root(N, precision=5):
2 P = lambda a, b: a * 10 ** (-b)
3 result = perfect_cube_root(N)
4 if result**3 == N:
5 return result
6
7 for i in range(1, precision + 1):
8 start = 0
9 end = 9
10 mid = (start + end) // 2
11
12 cube = lambda: (result + P(mid, i))**3
13
14 while start != mid:
15 if cube() > N:
16 end = mid
17 elif cube() < N:
18 start = mid
19 elif cube() == N:
20 return result + P(mid, i)
21
22 mid = (start + end) // 2
23
24 result += P(mid, i)
25
26 return round(result, precision)
```

Let us look at an example,

If we run `cube_root(16.003008)`

then it should return `2.52`

.

At first, the `cube_root`

will call `perfect_cube_root`

, and surely it will get the `2`

in return.

Now at `line 7`

we start for-loop for a range of [1, precision + 1] and initialize `start`

, `end`

and `mid`

as 0, 9 and 4.

Notice, `start`

, `end`

, and `mid`

are not decimals reason for that is just that I did not want to deal with float numbers. Calculating `mid`

with float values was a mess and, this approach makes it easier to capture a smaller value if it did not find any value, to form a result for perfect cube root.

Anyway, since `i = 1`

therefore here we're dealing with `10`

precision, means we're searching for perfect or small in between ^{-1}`2.0`

and `2.9`

, at this point when loop will take `start`

and `mid`

at `5`

, `start != mid`

will break the loop and will proceed for `10`

.^{-2}

Hence, it will start searching between `2.50`

and `2.59`

, in this the loop will find `2.52`

as a perfect match and, `line 20`

will execute, which will add `0.02 ( P(mid, i) )`

to `result`

and return it.

## Time and Space Complexity

### Time Complexity:

At first, we're performing purely a binary search which should take **O(logN)** time,

then after this, we perform binary search on space of [0, 9], for **P** times,

which will total to, **Plog(10)**

that is, **4P**.

therefore,

Time Complexity =

O(logN + P)

### Space Complexity:

The function itself takes one *Number* and creates a constant number of variables which use a constant number of space,

therefore,

- Space Complexity =
**O(1)**

With this article at OpenGenus, you must have the complete idea of Finding cube root using Binary Search.