𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tight bounds on the complexity index of one-point iterations

✍ Scribed by J.M. Trojan

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
516 KB
Volume
6
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Tight bounds on the complexity of the Ap
Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
✍ Maxime Crochemore; Thierry Lecroq πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 678 KB

The Apostolico-Giancarlo string-matching algorithm is analyzed precisely. We give a tight upper bound of $n text character comparisons when searching for a pattern in a text of length n. We exhibit a family of patterns and texts reaching this bound. We also provide a slightly improved version of the

Improving the efficiency index of one-po
Improving the efficiency index of one-point iterative processes
✍ J.A. Ezquerro; M.A. HernΓ‘ndez; N. Romero πŸ“‚ Article πŸ“… 2009 πŸ› Elsevier Science 🌐 English βš– 932 KB

A priori error estimates R-order of convergence Multipoint iterations Boundary value problem a b s t r a c t From the ideas of improving the speed of convergence and reducing the computational cost of one-point iterations, a new uniparametric family of multipoint iterations is constructed in Banach

On the cost of recomputing: Tight bounds
On the cost of recomputing: Tight bounds on pebbling with faults
✍ Yonatan Aumann; Judit Bar-Ilan; Uriel Feige πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 184 KB

We introduce a formal framework to study the time and space complexity of computing with faulty memory. For the fault-free case, time and space complexities were studied using the "pebbling game" model. We extend this model to the faulty case, where the content of memory cells may be erased. The mod