Depends which cost function you take into consideration. The size of the block part occupied by a multi-transaction would still be O(n) as are n transaction. So, yes, it could be cheaper by a factor of 2 or so.
A key thing that Nxt *has* over its rivals is fast txs. If I have a tx with 100 outputs and 1 sig vs. 100 outputs and 100 sigs then the latter is going to be slower both in terms of data size and sig verification.
Size maybe. Verification depends on the runtime complexity of the verification function.
Do not think that calculating 1 sig has constant runtime = O(1). It should be depend on the size of the to-be-verified payload.