I think only O(N²) opcodes would be affected (assuming removal of int limits). Imagine you want to do a few more OP_MULs but they'd be over the budget. Couldn't you add some <garbage> OP_DROP to inflate the TX size to reduce density and then squeeze in more calls to OP_MUL?

The push/drop consumes budget too, could one try to dodge it by inflating non-Script parts of TX (adding filler inputs/outputs). If yes, then we might consider counting output size as if it was a push op.