Complexity of self-reducible set
Suppose for simplicity that $|l(x)| = |r(x)| = |x|-1$. If $L(n),R(n)$ are the time complexities for computing $l,r$ on inputs of length $n$, then the time complexity for computing membership in $S$ satisfies the recurrence
$$ T(n) \geq L(n) + R(n) + 2T(n-1). $$
Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.

If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c &lt; 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).

So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.