I'm working on a problem that requires a sub-linear solution.A quick search for sub-linear will return a lot of this...... where the sub-linear line is modelled as logarithmic/asymptotic.But I had come to understanding that sub-linear was anything that remained below the linear baseline, as the both tended towards infinity. In this plot...... the sub-linear result is still linear-looking (i.e. y = mx + b), but falls below the linear baseline. So which is it? Does it have to be asymptotic/logarithmic? Or just trending away from the linear baseline solution?
Can sub-linear still be a straight line?
algorithms;performance;big o
No, it cannot be. It looks like it can from this graph because it is a log-log plot, which means both the x and y axes are compressed. Any function which satisfies the relation y = a*x^c for some constants a and c will appear as a straight line in a log-log plot. So the simple answer is the sub-linear case is not a straight line. This is evident from the legend too. The sub-linear case is labeled O(N^0.78). In a log-log plot, that would appear as a straight line with a slope of 0.78. However, it looks like this compared to a straight line in a regular plot: To be clear, it does not need to be logarithmic as you ask in the question. Any curve which grows slower than a straight line in the asymptotic case is sub-linear. A logarithmic curve is just an example.