$\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 Answer

$\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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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