How to use shadow mapping and deferred rendering to create a large amount of lights? Ok so I am trying to understand how to combine these 2 techniques and I am failing.

The main goal is to reach the O(lights+fragments) complexity of deferred rendering, instead of O(lights*fragments) of naive/forward rendering.

This is how I am currently doing things:

Say we have n lights. Then we generate n shadow maps O(n)

Now we do one render pass to generate the normal, diffuse color, depth.... information in the geometry buffers.

Then we check for every fragment whether it is occluded in ALL lights. and shadow it if it is.

This has an O(Lights*Fragments) complexity, which is wrong, so how can you reach the ideal asymptotic complexity? What should you do?
Deferred rendering does not have an asymptic complexity of O(lights+fragments). It has a complexity of O(fragments+visibleFragments*lights).

What you are doing in deferred rendering is preventing having to calculate lighting for many fragments that cover the same screen pixel. Once you have found which ones are visible, all of those still have to calculate lighting from every light source.

This is faster than forward rendering on the premise that lighting calculations are heavier than geometry calculations and that most fragments are ocluded by other fragments.