# General Root Computation (Root Computation)

## Description

Given a real continuous function, compute one of the roots.

## Parameters

$\epsilon$: (additive) tolerance error

$a, b$: endpoint values, with $b>a$

$n_{max}$: maximum number of iterations

## Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Bisection method 1820 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic
False position method 1690 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic
Secant method 1940 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic
Ridder's method 1979 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic Time
Muller's method 1956 $O(n_{max})$ $O({1})$ epsilon, additive Deterministic Time
Illinois Algorithm 1971 $O(n_max)$ $O({1})$ epsilon, additive Deterministic Time
Anderson–Björck algorithm 1973 $O(n_max)$ $O({1})$ epsilon, additive Deterministic Time
ITP Method 1940? $O(n_0+log((b-a)$/epsilon)) $O({1})$ epsilon, additive Deterministic
Steffensen's method 1940(?) $O(n_max)$ $O({1})$ epsilon, additive Deterministic
Inverse quadratic interpolation 1940(?) $O(n_max)$ $O({1})$ epsilon, additive Deterministic
Brent-Dekker Method 1973 $O(n_max)$ $O({1})$ epsilon, additive Deterministic Time