<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2018-01-03T18:34:21.243Z
What does miners do to verify balance of an account? For example, I send 1 BTC to Bob as a transaction, and I have 0.99 on my balance. So do miners accomplish this with O(n), in order to check I have enough balance? This will clear a lot in my mind. @Andrew Chow♦
alper
CC BY-SA 3.0
2018-01-03T19:04:00.270Z
There are no accounts in Bitcoin, only UTXOs. To validate a transation miners will sum the UTXOs referenced as inputs to that transaction. In Bitcoin users do not spend from accounts. They spend or use UTXOs.
Matthew Stannard
CC BY-SA 3.0
2018-01-04T00:34:07.743Z
@Alper, the transaction contains the exact place to find the outputs out spends, therefore it really doesn't have to search.  It already knows where to find what it is looking for.
Jestin
CC BY-SA 3.0
2018-01-04T07:11:54.030Z
So the transaction contains its block number its located? How a transaction knows the exact place to find the outputs to spend? @Jestin
alper
CC BY-SA 3.0
2018-01-04T07:16:56.640Z
No, transaction inputs refer to previous outputs by their txid. Nodes keep a database of all unspent outputs indexed by txid.
Pieter Wuille
CC BY-SA 3.0
2018-01-03T18:21:33.423Z
2018-01-03T18:21:33.423Z
Ava Chow
<p>Here is the Q/A related to: <a href="https://bitcoin.stackexchange.com/q/22997/44020">How is a wallet's balance computed?</a>. </p>

<p>Based on this:</p>

<p><strong>[Q]</strong> What is the Big-O complexity to retrieve the balance for a user? </p>

<p>Is it O(n), so basically do I have to iterate all <code>utxoset</code> 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?</p>

<p>Thank you for your valuable time and help.</p>

<wallet><utxo><balance>
What is the Big-O complexity to retrieve the balance for a user?
alper
# What is the Big-O complexity to retrieve the balance for a user?

(Asked by: username_0 on 2018-01-03)

Here is the Q/A related to: [How is a wallet's balance computed?](https://bitcoin.stackexchange.com/q/22997/44020).

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.

**Tags:** wallet, utxo, balance


---

## 1 answers

### Answer by username_1 on 2018-01-03. Score: 5 | Accepted answer

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).

> **Comments:**
> **username_0**: What does miners do to verify balance of an account? For example, I send 1 BTC to Bob as a transaction, and I have 0.99 on my balance. So do miners accomplish this with O(n), in order to check I have enough balance? This will clear a lot in my mind. @Andrew Chow♦  
> **username_2**: There are no accounts in Bitcoin, only UTXOs. To validate a transation miners will sum the UTXOs referenced as inputs to that transaction. In Bitcoin users do not spend from accounts. They spend or use UTXOs.  
> **username_3**: @Alper, the transaction contains the exact place to find the outputs out spends, therefore it really doesn't have to search.  It already knows where to find what it is looking for.  
> **username_0**: So the transaction contains its block number its located? How a transaction knows the exact place to find the outputs to spend? @username_3  
> **username_4**: No, transaction inputs refer to previous outputs by their txid. Nodes keep a database of all unspent outputs indexed by txid.  

---

