Notice that for GIS, the top loops end up iterating over all non-zero indicator functions, for each output, for each training instance.
they examine every entry in the training matrix T once, and thus require time T .