# Can “sub-linear” still be a straight line?

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?

• Technically, sub-linear complexity includes constant complexity, and the graph for constant complexity is a horizontal straight line. But by definition all asymptotically straight lines represent linear complexity – whether a line “falls below” another is not considered relevant. – amon Apr 25 '17 at 7:12
• Your sub-linear result can be "linear-looking" dependng on how you look at it but it is not like y = mx + b. – Goyo Apr 25 '17 at 8:21
• Per definition, a sub-linear solution can never be linear, since, if it was, it would be linear and hence not sub-linear. – Paul Kertscher Apr 25 '17 at 11:43

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.

• Note the scale on the graph in this answer. This is a linear graph rather than a log-log graph as shown in the question. – David Hammen Apr 25 '17 at 9:32
• @FabioTurati, note that the original plot was logarithmic on both axes (log-log). On a lin-log plot it would be the exponential that looks like a straight line. – ilkkachu Apr 25 '17 at 9:53
• @ilkkachu You are right. Sorry! – Fabio Turati Apr 25 '17 at 10:19
• Yup, I didn't even notice the log-log scale on the second plot. I reckon I would have asked the question either way. – Birrel Apr 26 '17 at 21:42

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?

Notice the scales on both the pixels and time axes. They are uniformly spaced, but in a logarithmic sense. Time goes from 0.1 seconds to 10000 seconds, plotted uniformly by powers of ten, and pixels go from 30000 to ten million, also uniformly in a logarithmic sense. That makes this a log-log graph. These kinds of graphs can be very useful for looking at data that spans multiple orders of magnitudes.

Given a relationship of the form T = kPN, this will appear as log(T) = N log(P) + k on a log-log graph. In other words, even a sublinear relationship will appear to be linear, but with a slope that is less than that for a linear relationship. Similarly, a superlinear relationship will also appear to be linear, but with a slope greater than that of a linear relationship.