The bottom loops also require time O(T ).
one iteration of SCGIS takes about as long as one iteration of GIS, and in practice in our im-plementation, each SCGIS iteration takes about 1.3 times as long as each GIS iteration.