As far as i understand rasterisation has a complexity of O(n) per pixel where n is the number of primitives in the scene. The acceleration structures used in ray tracing should make it O(log n) per pixel because the intersection test doesn't have to be done for all primitives.
So why isn't ray tracing faster than rasterisation?
Is the intersection test so much slower that it overweighs the advantage in complexity?
your complexity analysis is wrong as the stuff depends on more than just single parameter and their weights are very different between the two methods of rendering...
standard 2D rasterizer depends on:
where raytracer depends on:
The weight of the parameters also depends on used HW and rendering technique (order might change slightly).
However the major difference is you do not need to check each primitive on per pixel basis for rasterizer while raytracer needs to do it (even multiple times)...
Another aspect is used HW. Common GFX cards are designed for rasterization and raytracing is/was achieved with huge pain to overcome HW design (at least until compute shaders) you can look at it as HW accelerated vs. SW render speed difference.
both of the aspects are in favor for rasterization and that is why ratsterization performs better.
However Raytracing HW is finally starting to emerge (for few years now) and on that the raytracers are fast (even on relatively small clock like 66MHz FPGA)...
Rasterization does not have a complexity O(N) per pixel. It has a total complexity of O(NA) where A is the average area (in pixels) of the projected primitives. This is because a primitive "knows" where it projects and which pixels it will influence.
In typical cases, NA is on the order of the image size, let R². More precisely, the complexity is the image size times the average number of surfaces along rays (a few units), O(R²S).
Assuming efficient log(N) per ray queries (which is an optimistic estimate), ray-casting has a complexity of O(R²log(N)).
