Time complexity of API calls

+1 vote
Is there a page that lists time complexities of API calls? If not, how can I obtain this information? Do I have to go through source code and see how each call is implemented or is there a better way?
asked May 14, 2018 by TinfoilHat

1 Answer

+1 vote
Best answer

For the most part, the time complexity of an API command is linearly related to the input and/or output size (plus some possible fixed amount). But there are some exceptions, for example:

  • Any command which performs a significant rearrangement of the blockchain (e.g. setlastblock).
  • Many commands which relate to the wallet, including getting balances and building new transactions, grow in linear time with the number of UTXOs (unspent transaction outputs) in the wallet. This count can be obtained from getwalletinfo.
  • API calls that can perform an optional blockchain rescan (e.g. subscribe or importaddress) are linear in the number of blocks to be rescanned.
If you have a question about any specific API command, feel free to ask.
answered May 15, 2018 by MultiChain
selected Aug 30, 2018 by TinfoilHat
Hello and thank you for your answer. I'm mostly interested in calls related with storing and querying data. For example, what are the time complexities of
getstreamitem, getrawtransaction and getblock ? They all take hash strings as input if I'm not mistaken.
The time complexity of all these APIs is O(log n) where n is the number of items being retrieved from. This is because all use index lookups, and any general index has O(log(n)) complexity.