We do indeed expect a higher execution time, but higher by a constant factor. If the time for 100 rows is "time_100" and the time for 100c rows is "c*time_100" the order of complexity is still O(rows). A matrix is considered sparse when n = O(rows), so in our example the new matrix would have "c * n" triplets. Any factor applied to "rows" is applied to "n" and is applied to execution time. It is conventional to express complexity in terms of "n", which is why it was written instead of O(rows).
If the number of triplets is not proportional to the number of rows, then it is not a sparse matrix. That is, if you increase the size arbitrarily and the number of elements is constant then it is not a sparse matrix.