I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested). I'm asked to compare the theoretical results of the operations in amortized time, with the running times of my implementation. Now my question: since amortized times are based on the fact that we look not just at a single operation, but at a series of operations, what can I do with my implementation to receive some experimental results that support (or not) my theoretical analysis?

  • 2
    $\begingroup$ Try to find Catherine McGeoch's Guide to Experimental Algorithmics in a library near you. $\endgroup$ – adrianN Dec 20 '16 at 21:44
  • 1
    $\begingroup$ I find your question to be very broad. What can you do? Everything you want! What should you do? I don't know, what do you already have? Which kind of data structure are you analysing, and which kinds of sequences? $\endgroup$ – Raphael Dec 20 '16 at 22:47

If you want to compare theory and experiment, you have to perform both analyses under the same assumptions.

Note that this includes what you measure. Since you did not analyse time in theory, there is little sense in measuring running times in the experiments. Use combinatoric measures you can count reliably and independently of the system and its load.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.