# Tag Info

Lets look at the (worst-case) recurrence for bt: $$T(n) = \sum_{l = 1}^{n} (O(l) + T(n-l))$$ Here $n$ measures the length of the string passed to bt. The sum basically represents the complexity of the loop; for every $l$ you do a $O(l)$ compare operation and in the worst-case call bt with a string of length $n-l$. However we can simplify the above relation ...