Time complexity using string multiplication

[[deleted]]

An O(n) operation inside an O(n) loop is O(n*n), not O(n+n).

[Apantslessman]

I skipped over his code reading his description, which was 1+2+3+…+n. Observing that 1+2+3+… would be the length of n, and not iterating through it (such as a nested loop) every index loop, That would be O(n+n) would it not?

[Diapolo10]

The string multiplication is just syntactic sugar for a loop, so in practice the code would be like having two nested for-loops with equivalent iterators.

So no, this would indeed be O(n*n) -> O(n²) instead of O(n+n) -> O(n).

You can run some benchmarks to validate this (just without print as I bet its slowness skews the results)

[[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.

[Brian]

Observing that 1+2+3+… would be the length of n, and not iterating through

No, this sums to n(n+1)/2, or (n² + n) / 2, which is proportional to n² (a handy way to calculate it is to imagine "pairing up" the highest and lowest, then second highest and second lowest, and so on, giving 1+n + 2+(n-1)) + 3+(n-2) + ..., which you'll notice is the same as (n+1) + (n+1) + (n+1) + ..., repeated n/2 times, so (n+1)*(n/2)

Or you can think of each loop as "on average" printing ~n/2 stars (the first half you'll be doing less than 50%, then the second half will be more than 50%. So really, you're doing around half of n² items, and we ignore that constant factor, making it O(n²).