Assuming randomly-picked outputs, it's actually worse. The slowdown factor has to do with the depth of the tree, and TXO and STXO trees are always growing. It's still complexity O(log N), but with TXO/STXO N is the size of the entire block chain history, whereas with UTXO it's just the set of unspent transaction outputs.
Of course that's not a fair assumption since in an insertion-ordered tree using the Merkle mountain range data structure would have significantly shorter paths for recent outputs. But the average case might be about the same, and it comes with a slew of other tradeoffs that make it hard to compare head-to-head in the abstract. Ultimately both need to be written and benchmarked.
But it is not the case that TXO/STXO gives you constant time updates. The append-only TXO tree might be close to that, but you'd still need the spent or unspent tree which is not insertion ordered. There are alternatives like updating the TXO tree and requiring blocks and transactions to carry proofs with them (so validators can be stateless), but that pushes the same (worse, actually) problem to whoever generated or assembled the proof. It may be a tradeoff worth making, but it's not an easy answer...