I executed a linear search on an array containing all unique elements in range [1, 10000], sorted in increasing order with all search values i.e., from 1 to 10000 and plotted the runtime vs search value graph as follows:
Upon closely analysing the zoomed in version of the plot as follows:
I mainly have 2 questions:
1. Will piecewise regression will be a better idea to fit the data instead of linear regression, as the plot represents a step function (runtime is step function of search value) ?
2. In this case we are sure that when the step function breaks (or starts taking news values), we have NOISE, that may lower the accuracy of the model. So, should we consider this noisy data in our training dataset or exclude it and why ?
Clarification for what is NOISE : In the second screenshot, the runtime for some of the higher search values in lower than the runtime for lower search values and vice versa
Any suggestion is greatly appreciated!