All raytracing algorithms are based on some spatial subdivision structure (usually BVH based) which gets you O(logN) instead of O(N). Increasing poly count only gets interesting when you figure out how to compress truly huge scenes into a limited memory footprint.

Lots of different materials are difficult for GPUs because of divergence - if every ray spawned from a surface scattering event hits a different material you’ve lost all parallelism.

Lots of lights: Evaluating them all for a given surface scattering event is obviously an O(N) problem (for 10 lights no big deal, but what about thousands?), so you want to choose some small subset of “important” lights to consider. Making that choice is a hard problem because the correct choice depends on the product of the incident radiance from the light, the BSDF at the surface as well as the visibility function. There’s a lot of interesting research being done on this (Path guiding by learning the incident light field or its product with the bsdf, new sampling techniques, spatio-directional acceleration structures) at the moment.