In the worst case, when every feature chosen appears on every training example, then C/ T = 1, and the two algorithms essentially have the same running time.
in sparse feature spaces there is reason to believe that C/ T will be small for most iterations.