[kqr]

Prove running time as in complexity analysis is more analysis than algebra though, right?

[saagarjha]

Depends. There's not a whole lot of analysis you can do on sufficiently complex recursive algorithms.