[AlotOfReading]

It would only be O(n) if the number of additions was constant. Here it varies with the size of the multiplier, giving us O(n*m).