1

What does people mean when they say things like:

  1. Big O estimates scalability.

  2. The runtime grows “on the order of the square of the size of the input”, given that the algorithm in the worst case runs in O(n^2).

Does it mean for large n quadruple runtime for the doubled input size (assuming the algorithm runs in O(n^2))?

Is you said YES, then suppose that the number of steps our algorithm takes in the worst case is expressed by the function:

enter image description here

It follows that:

enter image description here

Moreover, we can see that:

enter image description here

But we can't quadruple runtime for the doubled input size n (even for large values of n) in this case, because it would simply be wrong. To see this, check the following plot:

enter image description here

And here is the plot of the ratio f(2n)/f(n):

enter image description here

It doesn't look like this ratio is tending towards 4.

So, what is scalabity, then? What does Big O estimate, if not the ratios like f(2n)/f(n) for large enough n? It doesn't seem to me that f scales like n^2.

mathgeek
  • 303
  • 1
  • 9
  • What kind of algorithm has `cos(n) ` complexity? That would mean that for some number inputs the runtime would be shorter than for fewer inputs. Please provide an example for that. – daniu Sep 22 '21 at 21:22
  • 1
    O(n^2) means that the asymptotic complexity of the algorithm is approximately n^2. In your first graph, the values around 20 are much smaller than any value around 60 and it isn't a linear increase. So if you wanted to plan for an `n` around 1000000 how much computing resource would you estimate you need? – Jerry Jeremiah Sep 22 '21 at 21:25
  • @daniu, I don't have an example for that. It is a theoretical question. Just assume that it is an algorithm that handles inputs of size ```2πk``` worse than other inputs. – mathgeek Sep 22 '21 at 21:26
  • @daniu What about a case where you don't log every item you work on because all you need is an indication that the algorithm is proceeding but it is the logging that takes all the resource. Then it could be that bigger inputs could be faster until you get to one of those input that logs something. – Jerry Jeremiah Sep 22 '21 at 21:28
  • 3
    Your first graph does a nice job of showing that the run time is bounded above by one scaled quadratic curve, and bounded below by a differently scaled quadratic curve. Hence it is Theta(N^2), end of story. – pjs Sep 22 '21 at 21:29
  • @Jerry Jeremiah, Thank you for the comment! But as I know Big O doesn't estimate resources. I mean benchmarks estimate resources. Big O should estimate scalability. But this word *scalability* seems confusing to me (I've explained in what sense in my question). – mathgeek Sep 22 '21 at 21:30
  • @pjs, Thank you, but you've just written what already was in my question) – mathgeek Sep 22 '21 at 21:32
  • @mathgeek Scalability means how much resource you need to have to scale the algorithm to larger input sizes. A more complex algorithm requires more resources for bigger inputs than a less complex algorithm. So you can estimate the scalability of an algorithm on the O() value. – Jerry Jeremiah Sep 22 '21 at 21:32
  • @Jerry Jeremiah, would you explain the meaning of "scalability" without referring to the word "scale"? – mathgeek Sep 22 '21 at 21:34
  • @mathgeek https://en.wikipedia.org/wiki/Scalability – user3386109 Sep 22 '21 at 21:41
  • People can say what they want, you don't have to listen. The word "scalability" means nothing. Ignore it until those people provide a rigorous definition. – n. m. could be an AI Sep 22 '21 at 21:43
  • @user3386109, I've already read it and it doesn't answer the posed question. – mathgeek Sep 22 '21 at 21:53
  • @1.8e9-where's-my-share m., thank you for the comment! But what should ```f(n) ∈ O(n^2)``` tell you in terms of your algorithm performance? The fact that there is some function ```Cn^2``` that is above of equal to your original function ```f(n)``` doesn't seem relevant to the actual performance of the algorithm. – mathgeek Sep 22 '21 at 21:55
  • The Big O notation is a way to write down sentences like "this function is bounded from above by this other function". That's what it does, that's what it is supposed to do, and that is what it should tell you. No more, no less. If someone tells you it characterises "performance", stop listening. – n. m. could be an AI Sep 22 '21 at 22:06
  • @1.8e9-where's-my-share m., it makes so much sense, but it means that being in ```O(n^2)``` doesn't tell us anything about how the actual runtime will increase if we double the input size, does it? According to my example, it can increase in a different way than ```n^2```. We only know that if ```f ∈ O(n^2)```, then ```f``` can't always keep increasing faster (or slower) than ```n^2```, right? I mean if ```f``` sometimes increases faster than ```n^2``` it's going to slow down somewhen so that it increases at the same pace as ```n^2```? Sorry if it's too confusing – mathgeek Sep 22 '21 at 22:51
  • @mathgeek: "Big O" is nothing more than a crude estimate (not an accurate prediction). For small N it can be very wrong because the cost of an "O" is ignored. For large N it can be very wrong because artifacts of the memory hierarchy (cache misses, TLB misses, swap space accesses) are ignored. Just assume "big O" is always very wrong and you'll be fine. – Brendan Sep 23 '21 at 00:44
  • @Brendan, thank you for the answer, but I could say so about everything in the world. But my question isn't asking about the meaning of Big O. It's actually very simple. I can restate it like this: ***A***: "What is scalability?", ***B***: "It is the way your function increases when you increase the input. E.g. if ```f ∈ O(n^2)``` then doubling your input means quadrupling the runtime (output)". ***A***: "Consider function f(n) = n^2(cos n + 2). Your statement never holds for f. You never quadruple the runtime for the doubled input. It implies that **scalability** means smth else. What, then?" – mathgeek Sep 23 '21 at 00:53
  • 1
    Let me reiterate. Scalability is a vague term with no rigorous definition. If you are after rigorous definitions, just ignore it. – n. m. could be an AI Sep 23 '21 at 04:54

1 Answers1

4

So, what is scalabity, then? What does Big O estimate?

Big-O notation gives an upper bound on asymptotic complexity for e.g. classifying algorithms and/or functions.

Does it mean for large n quadruple runtime for the doubled input size

No, you are mixing up asymptotic (time) complexity with actual "runtime count" of your function. When deriving the asymptotic complexity in terms of Big-O notation for, say, a function, we will ignore any constant terms, meaning that for your own example, f(n) and f(2n) are identical in terms of asymptotic complexity. Both for f(n) and for g(n) = f(2n), f and g grows (scales, if you wish) quadratically in they asymptotic region. This does not mean their runtime is exactly quadrupled for a doubled input size (this kind of detailed hypothesis doesn't even make sense in term of asymptotic behavior), it only governs an upper bound on growth behavior for sufficiently large input.

Refer e.g. to my answer to this question for more thorough explanation on the non-relevance on both constant and lower order terms when deriving asymptotic complexity for a function:

dfrib
  • 70,367
  • 12
  • 127
  • 192
  • Thank you for the answer! But why is Big O useful, then? Suppose ```f(n) ∈ O(n^2)```. It just tells you that there is some function ```Cn^2``` that is above of equal to your original function ```f(n)``` for large enough values ```n```. It doesn't tell you anything about how ```f(n)``` actually scales (whatever it means). – mathgeek Sep 22 '21 at 21:51
  • @mathgeek That's an entirely separate question, and I usually try to avoid answering new questions (that could be likewise posted) in the comments. But in short: in a _real_ product program, you need to _measure_ to find bottlenecks, and to find whether these are even an issue. When _designing_ parts of your program, you should take into account any limitations of your target hardware. Some may have limitations in space, some may have limitations in time. These are both input e.g. when choosing a sorting algorithm for a, in context, very large container. I would like to emphasize though ... – dfrib Sep 22 '21 at 21:57
  • ... that my experience is that asymptotic analysis is very much an academic topic, that _seldom_ shows up in practice, more than it being essential to know what the terminology means, e.g. when making a space-time decision when choosing which STL container to use. In practice, measurements with a profiler is your truth, and anything beyond that, including Big-O analysis, is strictly theoretical. An _amortized_ O(1) lookup may loose out horribly to a O(n) lookup due to low-level details such as cache misses and so on. If you are, however, designing some state of the art algorithm say, for ... – dfrib Sep 22 '21 at 21:59
  • ... a paper to be published, that it is naturally essential to find _some_ theoretical metric on how your algorithm performs as compared to other algorithms used in the same problem domain. Asymptotic complexity is _one_ such measure. Another one could be actually profiling a lean implementation of the algorithm over a set of industry-standard problems for the particular problem domain; this is common e.g. in operations research where many problems are NP-complete and we are way beyond "this problem can be solved in quadratic or cubic time". – dfrib Sep 22 '21 at 22:01
  • 1
    @mathgeek: I regularly encounter algorithms in the real world, where Algorithm A might "feel" slower than Algorithm B, but when I point out that A has a lower big-O, every developer is immediately convinced that A is the better choice. This comes up often when Algoirthm A involves iterating over a hashmap. That "feels" slow and wrong, but it's still linear time, so better than any O(NlogN) algorithm for large inputs. – Mooing Duck Sep 22 '21 at 22:02
  • 1
    @MooingDuck And, conversely, I regularly encounter cases where the input is sufficiently small for low-level memory details let a contiguous storage container with linear lookup totally lay waste to say a hashmap, as the context may e.g. moreover mutate the containers. Whilst knowing what and what not Big-O notation describe is essential for particularly picking e.g. existing container and algorithm implementations, it is likewise important to know the the Big-O metrics for these are based on _basic operations_ that may be way too high-level in the actual problem domain (caching effects etc). – dfrib Sep 22 '21 at 22:15
  • @Mooing Duck, Owner of the answer, Excuse me for possible confusion, but I very well understand that "comparing between different Big O classes" part. It follow from the mathematical definition why ```f ∈ O(n)``` is eventually faster than ```g ∈ O(n^2)```. But I've encountered tons of statements like "being in ```O(n^2)``` tells you how your algorithm runtime scales when you increase the input size". As I understood they all must claim that from ```g ∈ O(n^2)``` you should know what the ratio ```g(2n)/g(n)``` is gonna be for large ```n```. But I showed in my question that it's wrong. – mathgeek Sep 22 '21 at 22:35
  • In what sense they use the word "***scale***", then? It is my original question that still confuses me. – mathgeek Sep 22 '21 at 22:36
  • If it's more convenient, please, write an addition to your answer or just answer in comments (at your discretion). – mathgeek Sep 22 '21 at 22:39
  • 1
    @mathgeek "But **I've encountered** tons of statements like "being in O(n^2) tells you how your algorithm runtime scales when you increase the input size" / "In what sense **they** use the word scale, then?" - to be blunt I'm starting to wonder whether this answer and my comments above is a waste of time, as it seems you wish for us to try to look into the minds of these other sources, and how your interpret ”scale”. If so, this whole question becomes opinion-based, and should be closed. Big-O notation is what it is, but it seems as if you are looking for a different metric. (-> I'm out) – dfrib Sep 22 '21 at 22:39
  • I just thought it was a common thing to assume and would be easy to clarify, accept or negate. – mathgeek Sep 22 '21 at 22:56
  • @mathgeek it is not easy to clarify. It's basically "as the input gets *much* larger, how much slower will the algorithm get, *extremely* roughly". Scale here only has the mathematical definition that you already quoted, it doesn't really have any practical, easy to understand concept that it represents. – Mooing Duck Sep 23 '21 at 18:21
  • @Mooing Duck, Do you mean that if f(n) ∈ O(n^2), then it's a common practice to just assume f(n) = kn^2 (which is just an approximation that sometimes can be very wrong)? – mathgeek Sep 23 '21 at 20:32
  • I mean that if f(n) ∈ O(n^2), then it's a common practice to just assume f(n) ~ kn^2, , which is just an approximation that is sometimes can be very wrong, but also assume that f(n) < kn^2, which is just an approximation that is always correct. – Mooing Duck Sep 24 '21 at 16:21