# Piecewise defined polynomial time complexity?

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.

• My initial guess is cache effects. ​ ​ – user12859 Jun 12 '17 at 5:04
• 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. – David Jun 12 '17 at 5:14
• It's probably an implementation artifact (combined with a cache effect) - not necessarily yours (could be the library's). – Yuval Filmus Jun 12 '17 at 7:37
• This question is impossible to answer given the given data. – Yuval Filmus Jun 12 '17 at 7:37
• 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) . ​ ​ ​ ​ – user12859 Jun 12 '17 at 9:36