How can we assert that the performance of an implementation matches the expected performance defined in terms of Big-$\mathcal{O}$ and friends by generating best/worst case inputs? I'm thinking of a table whose columns are input length, expected running time, actual running time. Are there general methods for generating inputs for evaluation?

  • 1
    $\begingroup$ I think that in general, it's impossible to generate worst case inputs, because they can depend on the algorithm, its implementation and even hardware. $\endgroup$ – svick Sep 16 '12 at 10:29
  • $\begingroup$ I think the question is way too broad. First, the answer will depend on the kind of problem you are thinking of. It is also always algorithm-dependent (what do you think will be difficult for your algorithm?). Maybe in general, you could be thinking of instances that are generated randomly (i.e., maybe random graphs) and instances that come from real applications (if any). $\endgroup$ – Juho Nov 13 '16 at 9:56

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.