Summary: A new analysis of sequential decoding is presented that is based on the requirement that a set probability of error \(P_ e\) be achieved. The error criterion implies a bounded tree or trellis search region; the shape of this is calculated for the case of a binary symmetric channel with crossover probability \(p\) and random tree codes of rate \(R\). Since the search region is finite at all combinations of \(p\) and \(R\) below capacity, there is no cut-off rate phenomenon for any \(P_ e>0\). We calculate the decoder delay (search depth), path storage size, and the number of algorithm steps for several methods of tree search. These include searches without backtracking and backtracking searches that are depth- and metric-first. The search depth of the non-backtracking decoders satisfies the Gallager reliability exponent for block codes. In average paths searched, the backtracking decoders are much more efficient, but all types require the same peak storage allocation. Comparisons are made to well-known algorithms; in order of efficiency from best to worst these are Fano-like algorithms, the stack algorithm, algorithms like the \(M\)-algorithm, and the Viterbi algorithm.