I think maybe it's been too long since I last did analysis of algorithms … the only sensible meaning that I can assign to 'sub-constant' is that the contribution tends to `0` as the input grows; but it seems to me that `8 mb/thread * ≥ 1 thread` is certainly `Ω(1)`. (Or maybe I just missed a dry joke?)
8 MB is constant, but the number of bits in the input grows like log of the largest input value, so the 8mb overhead contribution goes down as the input grows.
Of course, the kernel isn't going to support more than 64 bits of sleep times any time soon, so it's okay if you want to say it's constant. ;-)
constant in the number of elements, sub-constant in the size of the input
I think maybe it's been too long since I last did analysis of algorithms … the only sensible meaning that I can assign to 'sub-constant' is that the contribution tends to `0` as the input grows; but it seems to me that `8 mb/thread * ≥ 1 thread` is certainly `Ω(1)`. (Or maybe I just missed a dry joke?)
8 MB is constant, but the number of bits in the input grows like log of the largest input value, so the 8mb overhead contribution goes down as the input grows.
Of course, the kernel isn't going to support more than 64 bits of sleep times any time soon, so it's okay if you want to say it's constant. ;-)
2 replies →