[amelius]

From an asymptotic complexity viewpoint, I don't see any difference between the two algorithms (AD versus building an expression tree and doing it symbolically, then evaluating). Both are linear in the "size" of the expression. So I don't understand what you mean by "quickly explodes".

[tome]

See here:

http://h2.jaguarpaw.co.uk/posts/why-is-naive-symbolic-differ...

In summary, yes both functions are linear, but the size of the symbolic derivative is quadratic.

[vidarh]

The result of the symbolic derivation grows faster than linearly, as you can see from the Product rule for example.

As a result, while the evaluation is linear with input tree size, the tree it is evaluating is typically much larger than the input expression.