1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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."? $\endgroup$ – user1781024 Sep 3 '15 at 6:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Tung Sep 3 '15 at 6:41
  • $\begingroup$ 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. :-| $\endgroup$ – user1781024 Sep 3 '15 at 6:49

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.