> There are two principal ways of applying asymptotic analysis to algorithms: time or memory used. It is usually both, but I meant time, because to be able to

> There are two principal ways of applying asymptotic analysis to algorithms: time or memory used. It is usually both, but I meant time, because to be able to address your stack frame you need* a stack pointer that can take as many distinct values as your nesting depth, so it must have o(log n) width. It is easy to dismiss this as irrelevant because your integers are usually fixed-width, but then you'd need to parameterize your algorithm on the size of input you're willing to handle (at which point you're no longer doing asymptotic analysis), since arbitrary-precision arithmetic really does just work this way normally. > Also, regarding "without tail calls", your example already has tail calls. What do you mean by that? I mean "without tail call optimization", or if you're particularly keen on getting into a pedant-off, "with the function call in the tail position not implemented as a tail call".