Update the complexity section.

This is still mostly a pro forma update, chasing through the
factor of log(p) that we have eliminated earlier.  I still
need to actually check the results for correctness and we need
to expand various parts.
Replace "soft O" by the symbol.
Introduce a TODO for a remark after Prop 7.4.