Root Computation (Root Computation)

Description

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

Parameters

No parameters found.

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
Newton's method	1940	$O(n_{max})$	$O({1})$	epsilon, additive	Deterministic
Halley's method	1940	$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
Householder's Method	1940(?)	$O(d*n_max)$?	$O(d)$	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