If you have a symbol that cannot be in the input (an EOT token), I think you can write it in O(1). You just change the input when you're done checking the outer symbols. Takes extra time, though.