of course cube root of N grow faster.
For instance, when N is equal to 1000000, log N is about 20,
while N^(1/3) is about 100
ngandhi
I'm still kind of confused about how we got O(cube root of N)? So if we have N^3 voxels, is it saying basically that we only have to pass through cube root of N many voxels and check intersections there?
FeiFeiFei
Yes. Actually you can see is the number of voxels to check is between cube root of N and 2 * cube root of N, which is O(cube root of N). And if the primitives per voxel is constant, then the total time complexity is still O(cube root of N).
of course cube root of N grow faster. For instance, when N is equal to 1000000, log N is about 20, while N^(1/3) is about 100
I'm still kind of confused about how we got O(cube root of N)? So if we have N^3 voxels, is it saying basically that we only have to pass through cube root of N many voxels and check intersections there?
Yes. Actually you can see is the number of voxels to check is between cube root of N and 2 * cube root of N, which is O(cube root of N). And if the primitives per voxel is constant, then the total time complexity is still O(cube root of N).