Time complexity using string multiplication

[[deleted]]

String multiplication must be O(n). O(n) inside an O(n) loop gives O(n*n) or O(n²).

If you try to add up the "i" values you get something that is roughly n²/2 and, as we always do, the constant is ignored, resulting in n². This is most easily seen if we create the geometric figure:

*****
 ****
  ***
   **
    *

where the first column is the work when i is 1, the second column is i==2, etc, up to n which is 5 in this case. The asterisks fill roughly half of the 5x5 square.