To assess the complexity benefit of bracketing we can extend the analysis of Section 4.8, making use of the recursive structure of the algorithm.
In the standard parsing scheme, the time complexity is 
for an
input of length l.
Hence, in the recursive scheme each bracketed substring takes time
, where r is the number of constituents in the substring
(which may be either input symbols or nested constituents).
The total number of bracketings in a given input string is O(l).
If R is an upper bound on r the total time is therefore 
.
In a fully bracketed input string each grammar rule used
in the derivation is reflected in a corresponding bracketing.
Hence, r is bounded by the maximal production length of the grammar,
and the time complexity is simply O(l).
}