1. Immediate lighting rasterizer = O(S*N*L)
2. Deferred lighting rasterizter =O(S*N)+O(S*L)
3. Ray tracer = O(S*log N*L*D)
where N is the number of solid 3D elements, L is the number of direct illumination lights, D is the indirect lighting depth and S is the number of screen elements.
No matter how I look at this, ray tracing is not very compelling.
Once upon a time, we thought ray tracers were fast. If we hold screen size as a constant and set the number of bounces to 1 for a fair comparison to a 1992 era rasterizer we get the "classic" complexity analysis comparison.
1. Rasterizer = O(N*L)
2. Ray tracer = O(log N*L)
Winner: ray tracer. However, a few things have changed since 1992. First, screen size is important and should not be ignored. This is due to the increasing importance of screen space effects. Second, deferred lighting broke rasterization in half. Third, rasterizers can now do convincing shadows and fake global illumination. So, to keep up with the quality of the average 2010 rasterizer we have to set D>1. This is a 1-2-3 knockout combo for ray tracers.
Rasterizers are the current complexity king. Now, I'll tell you why it will remain the king. Ray tracers have an architecturally bad design. It looks like this:
for p in rays:
for i in items: raytest
for s in lights:
for t in bounces:
There is a beautiful elegance to this. It is a good way to learn how to do computer graphics. Unfortunately, this kind of architecture always leads to bad complexity that looks like this: O(f1*f2*f3*f4
Rasterizers have a better basic architecture. Scatter-gather type architecture tends to lead to nice complexity like this: O(f1)+O(f2)+O(f3)+O(f4). Don't take my word for it, look at the history. The O(N*L) immediate rasterizer got broken up into the O(N)+O(L) deferred rasterizer as soon as enough memory became available. Indirect lighting followed the same pattern.
I'm not saying that ray tracers will always be slow. But, I _am_ saying that if ray tracers ever become fast again, it will be because they have been architecturally restructured into something that looks a lot like a rasterizer. In such a case, any claimed victory by the ray tracer would be a pyrrhic one.