1

I was reading about bucket sort and then I came to the following statement:

"As long as the input has the property that the sum of the squares of the bucket sizes is linear in total number of elements ..."

What does it actually mean? Suppose total number of elements is $10$. Then what set of numbers satisfy the statement, "$x$ is linear in $10$."

Gerry Myerson
  • 179,216
user1781024
  • 119

1 Answers1

1

Loosely speaking, it means that asymptotically, one quantity goes up in direct proportion to the other.

In the example you give, it means that if you double the number of elements, you (roughly) double the sum of the squares of the bucket sizes; if you triple one, you (roughly) triple the other; and so on.

Brian Tung
  • 34,160
  • Would I be wrong if I understand it as: "As long as x is equal to 10 or less than 10, it is linear in 10. Similarly as long as x is equal to 20 or less than 20, it is linear in 20."? – user1781024 Sep 03 '15 at 06:39
  • 1
    I don't think it would make much sense to most readers to say that a given variable $x$ is linear in some constant (say, $10$). There's no generally understood sense in which a variable can be said to be directly proportional to a constant. So I don't think I would say that you were wrong so much as I would say I don't really understand what you mean. – Brian Tung Sep 03 '15 at 06:41
  • Ohh, I got it. By giving just one instance (x, 10) I cannot talk about linearity. I need at least two instances to talk whether it is linear or something else. Like I can say (x, 10) and (2*x, 20) shows a linearity. But just taking one instance and predicting whether its linear or quadratic or something else is senseless. Isn't it? Also please bear with the poor formatting, I don't know how to make variables and constants bold here. :-| – user1781024 Sep 03 '15 at 06:49