Complexity of signing is O(1).
That is plain wrong. The more bits you have to sign the longer signing takes. The question is: how long in terms of the input length.
We would have O(n) if Sign(32_bytes) == Sign(64_bytes) / 2. Actually we have Sign(32_bytes) == Sign(3200_bytes) / 2, so it's more like O(1). Right?