# Q&A: Which is Faster, Bisection or Newton’s Method?

*Cross-posted from here.*

## Question

I read that Newton’s method is faster than bisection, but for comparing speed of the bisection method with Newton’s method, I just tried the corresponding Python functions like this:

```
import numpy as np
from scipy.optimize import bisect, newton
import time
# Define an example function
def f(x):
return x**3 - 2
# Bisection method
start_time_bisection = time.time()
root_bisection = bisect(f, 1, 2)
end_time_bisection = time.time()
time_bisection = end_time_bisection - start_time_bisection
# Newton's method
start_time_newton = time.time()
root_newton = newton(f, 1.0)
end_time_newton = time.time()
time_newton = end_time_newton - start_time_newton
# Print results
print("Bisection Method Result:", root_bisection)
print("Newton's Method Result:", root_newton)
print("Bisection Method Time:", time_bisection)
print("Newton's Method Time:", time_newton)
```

The results on my laptop were:

```
Bisection Method Result: 1.2599210498951834
Newton's Method Result: 1.2599210498947795
Bisection Method Time: 2.0265579223632812e-05
Newton's Method Time: 0.00040721893310546875
```

In this case, the bisection method was faster.

## Answer

The example you gave comparing bisection and Newton’s method is not a fair comparison. Sure, bisection ran faster for you, but Newton’s method produced a more accurate result by at least several orders of magnitude (you’re not holding the level of precision constant, so it’s not an apples-to-apples comparison). Additionally, you didn’t supply any information about the derivative into Newton’s method, so you’re artificially hamstringing it to use a difference approximation (which takes longer).

To find the root of $x^3-2$ a proper comparison would be to compare iterating the function `update_newton(x) = 2/3 * (x + 1/x^2)`

versus `update_bisection(bounds) = [bounds[0], m] if m**3 > 2 else [m, bounds[1]]`

(where `m = (bounds[0]+bounds[1])/2`

) until the desired level of convergence.

Doing this, we see that Newton’s method is in fact faster.

```
Num Trials: 1000
True Root: 1.259921049894873191
Epsilon: 0.000000000001000000
Bisection Method Result: 1.259921049895638134
Newton's Method Result: 1.259921049895406320
Bisection Method Time: 0.000012086868286133
Newton's Method Time: 0.000001034021377563
```

Here’s the script:

```
import time
def update_bisection(bounds):
mid = (bounds[0] + bounds[1]) / 2
if mid**3 > 2:
return [bounds[0], mid]
else:
return [mid, bounds[1]]
def update_newton(x):
# f(x) = x^3 - 2
# x - f(x) / f'(x)
# x - (x^3 - 2) / 3x^2
# x - 1/3 x + 2/3 x^2
# 2/3 x + 2/3 x^2
return 2/3 * (x + 1/x**2)
root = 2**(1/3) # = 1.2599210498948732
epsilon = 0.000000000001
num_trials = 1000
sum_results_bisection = 0
sum_results_newton = 0
def run_bisection():
global sum_results_bisection
guess_bisection = [1, 2]
while abs((guess_bisection[0] + guess_bisection[1]) / 2 - root) > epsilon:
guess_bisection = update_bisection(guess_bisection)
sum_results_bisection += (guess_bisection[0] + guess_bisection[1]) / 2
def run_newton():
global sum_results_newton
guess_newton = 1.5
while abs(guess_newton - root) > epsilon:
guess_newton = update_newton(guess_newton)
sum_results_newton += guess_newton
start_time_bisection = time.time()
for _ in range(num_trials):
run_bisection()
end_time_bisection = time.time()
start_time_newton = time.time()
for _ in range(num_trials):
run_newton()
end_time_newton = time.time()
time_bisection = (end_time_bisection - start_time_bisection) / num_trials
time_newton = (end_time_newton - start_time_newton) / num_trials
result_bisection = sum_results_bisection / num_trials
result_newton = sum_results_newton / num_trials
num_decimals = len(str(root))
format_str = "{:." + str(num_decimals) + "f}"
def format_decimal(x):
return format_str.format(x)
print("Num Trials: ", num_trials)
print("True Root: ", format_decimal(root))
print("Epsilon: ", format_decimal(epsilon))
print("")
print("Bisection Method Result:", format_decimal(result_bisection))
print("Newton's Method Result: ", format_decimal(result_newton))
print("")
print("Bisection Method Time: ", format_decimal(time_bisection))
print("Newton's Method Time: ", format_decimal(time_newton))
```