That transaction processing is subject to the market does not eliminate the requirement (in my view) to understand its algorithmic performance characteristics.
[/quote]

 - I'm a client, I broadcast a transaction to the network and all of its miners,
 - I'm a miner, I get the transaction, I include it in my merkle tree (inexpensive), and I keep mining. The mining algorithm is basically brute force SHA hashing on a fixed size message, so it's o(1) in relation to the number of transactions that are included in the currently mined block.
 - If I find a block I broadcast it (see research on P2P technology in relation to performance/thoughput/you name it)
 - A block is broadcast to me, I update my merkle tree and root and I keep crunching (every 10 minutes on average), I would (maybe naively) assume that the merkle tree update is o(n) in relation with the number of transactions that were previously included in the candidate block

Hmm, writing this post I'm starting to think it might be nice to have a full fledged, peer reviewed, detailed, and thorough analysis of all the factors that need to be balanced for optimal performance but that doesn't change my main opinion which is that bitcoin won't be good at micro-payments.