# The time complexity of finding the kth smallest number using buckets

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];
}
for (let j = 0; j < buckets[i].length; j++) {
numbers.push(buckets[i][j]);
}
}
return nthSmallest(numbers, k, sizeOfInt - 4);
}


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.
• 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? Mar 26 '19 at 17:35
• @Jorayen $O(nw/4)=O(nw)$. You may want a more smart solution. Mar 26 '19 at 17:43