0
$\begingroup$

I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where current is a value starting possibly at 64 (for 64 bits integers at most) and decrements each iteration by 4 (nibble size).

I was wondering what is the time complexity (worst) of this implementation. I think it's O(n^log64/4) which is O(n^16), is that correct?

function nthSmallest(array, k, sizeOfInt) {
    let buckets = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
    // put numbers in buckets - O(n)
    for (let i = 0; i < array.length; i++) {
        const high = (array[i] >> sizeOfInt - 4) & 0xF; // 4 = nibble size
        buckets[high].push(array[i]);
    }
    let numbers = [];
    for (let i = 0; i < buckets.length && numbers.length < k; i++) {
        if (numbers.length === k - 1 && buckets[i].length === 1) {
            return buckets[i][0];
        }
        for (let j = 0; j < buckets[i].length; j++) {
            numbers.push(buckets[i][j]);
        }
    }
    return nthSmallest(numbers, k, sizeOfInt - 4);
}
$\endgroup$
1
$\begingroup$

Your algorithm is a variant of the radix sort.

Consider $k=n$ and the greatest two numbers differ by only the least 4 significant bits, then the two greatest numbers will be always in the last buckets in each iteration except the last. This means you have to iterate for sizeOfInt, sizeOfInt - 4, ... until 4, so the overall complexity is $O(nw)$ where $w$ is sizeOfInt.

$\endgroup$
  • $\begingroup$ Shouldn't it atleast be O(nw/4)? Also how do it compares to other solutions for the problem like max-heap or using partial quicksort? Should I consider using this over partial quicksort for example since it's O(n^2) worst case? $\endgroup$ – Jorayen Mar 26 at 17:35
  • 1
    $\begingroup$ @Jorayen $O(nw/4)=O(nw)$. You may want a more smart solution. $\endgroup$ – xskxzr Mar 26 at 17:43

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.