As part of my research, I have recently written an algorithm for mining medical data. We are looking to potentially publish some of the data we collected however I would like to describe the algorithm I used in detail.

I was really curious about the algorithm so I recently programmed a dummy data generator and tested the algorithm. To my surprise, a simple plot of overall time vs. N (number of input arrays) yielded an almost perfect polynomial fit below N = 100000 and a secondary almost perfect polynomial fit at N >= 100000.

I am curious about potential explanations for this behavior and would be interested in learning more.

  • 1
    $\begingroup$ My initial guess is cache effects. ​ ​ $\endgroup$ – user12859 Jun 12 '17 at 5:04
  • $\begingroup$ I was thinking something along those lines too. It would seem oddly coincidental that a jump in efficiency is seen at N = 100000. The input data is in the form of Pandas DataFrames. $\endgroup$ – David Jun 12 '17 at 5:14
  • $\begingroup$ It's probably an implementation artifact (combined with a cache effect) - not necessarily yours (could be the library's). $\endgroup$ – Yuval Filmus Jun 12 '17 at 7:37
  • $\begingroup$ This question is impossible to answer given the given data. $\endgroup$ – Yuval Filmus Jun 12 '17 at 7:37
  • $\begingroup$ Depending on how sharp the transition is, another possibility is that your $\hspace{1.47 in}$ complexity is something like ​ N$^2$ + (100000$\cdot$N) . ​ ​ ​ ​ $\endgroup$ – user12859 Jun 12 '17 at 9:36

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.