Here is the Q/A related to: How is a wallet's balance computed?.
Based on this:
[Q] What is the Big-O complexity to retrieve the balance for a user?
Is it O(n), so basically do I have to iterate all utxoset to find matching outputs which correspond to public keys that it has the private key for ("your keys")? or is there any hash machanism that returns all outputs when I just provide my public-key?
Thank you for your valuable time and help.
It depends on what data structure you have put the UTXO set into. Different implementations do this in different ways, there is no one way to have the UTXO set.
For instance, one implementation may not maintain a UTXO set but rather iterates through the entire blockchain. This would be O(n) where n is the number of TXOs in the blockchain.
Other implementations may have the UTXO set in a list, so finding a balance would still be O(n) where n is the number of UTXOs because it has to iterate through the list.
An implementation could also make a map keyed on the scriptPubKey. The value would be a list of corresponding outputs (i.e. the amount and location). Then finding the balance of an address would be O(1+k) where k is the number of UTXOs for that address. This is significantly less than O(n) since looking up which UTXOs is O(1), but you still have to iterate through all of them.
So the time complexity of this really depends on the implementation, there is no one way to do it that all software use. In most implementations though, it is probably going to be O(n).
