How to use shadow mapping and deferred rendering to create a large amount of lights?
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.