New answers tagged


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 ...

Top 50 recent answers are included