5

I'm working on a problem that requires a "sub-linear" solution.

A quick search for sub-linear will return a lot of this...

Sub-linear #1

... 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...

Sub-linear #2

... 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?

  • 5
    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
  • 2
    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
27

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: enter image description here

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.

  • 1
    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
3

In this plot...

Sub-linear #2

... 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.