I would like to know the computational cost of using/accessing a dictionary.
This should depend on the length of the dictionary. Say a dictionary $D$ has $n$ elements.

What would be the cost of accessing one of those elements in terms of simple floating point operations (addition, subtraction, multiplication, division)?

  • 1
    $\begingroup$ This really depends on how the dictionary is implemented, and how exactly you are using it. The number of floating point operations might even be zero. $\endgroup$ – Yuval Filmus Mar 8 '18 at 23:35
  • $\begingroup$ I'd say that most common implementations use hash tables or balanced search trees. Neither involves floating point operations (at most, a hash table might compute the current load as a fraction, using one division which might be floating point). What makes you think that floating point operations are relevant here? $\endgroup$ – chi Mar 9 '18 at 20:26
  • $\begingroup$ I think I should clarify. The dictionary can use whichever implementation it likes. I would like to know what the computational cost of accessing a dictionary is. For example, say I wanted to run a simple program that starts with 1 and while it has done less computational work than to access a dictionary, it adds 1 on each iteration. What would this simple program output as the final result? So how many additions could I do with the same amount of computational power it takes to access a dictionary? $\endgroup$ – Abby Apr 10 '18 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.