Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
One-pass algorithm
open-in-new
<p>In computing, a one-pass algorithm or single-pass algorithm is a <a href="/facts/Streaming_algorithm/BjSCe5rR">streaming algorithm</a> which reads its input exactly once. It does so by processing items in order, without unbounded <a href="/facts/Buffer_(computer_science)/tVy4j2Dc">buffering</a>; it reads a block into an <a href="/facts/Input_buffer/tVy4j2Dc">input buffer</a>, processes it, and moves the result into an output buffer for each step in the process. A one-pass algorithm generally requires <i>O</i>(<i>n</i>) (see <a href="/facts/Big_O_Notation/weFFjSWg">'big O' notation</a>) time and less than <i>O</i>(<i>n</i>) storage (typically <i>O</i>(1)), where <i>n</i> is the size of the input. An example of a one-pass algorithm is the Sondik <a href="/facts/Partially_observable_Markov_decision_process/rbARkAXc">partially observable Markov decision process</a>. </p>