What causes quadratic hash problem?

Question

I read ScriptSig content during signature (quadratic hashing) discussing quadratic hash problem.

Quadratic hash problem is the issue that signing (or verifying) transaction time grows with the square of the number of inputs (O(n^2) where n is the number of inputs).

Why is that so? I reason the following:

1. For each input you construct different template. O(n)
2. This template must be double-SHA-hashed. - Double-SHA-hash duration is dependent linearly on the size of the template?
3. Double hashed template (of fixed length) is then signed. - as the leght is fixed this step is of fixed duration

As step 2 is dependent linearly on the size of the template, thus it is linearly dependent on the number of inputs, giving final time dependency relation O(n^2)?

More precisely O(n^2+m) where m is the number of outputs (as this contributes in step 2)?

Answer 1

Double-SHA-hash duration is dependent linearly on the size of the template?

Yes, of course.

So, increasing the count of inputs twice we also increase the size of each template ~twice and the work for signing/verifying whole transaction increased quadratic