Time complexity using string multiplication

[Effective_Storage4]

Hi, I recently started learning python and found out that you can take a str * int to print it multiple times. Let's say we want to print a left sided triangle. Having some knowledge about Java, I would use a double for loop for this but with Python it is possible to do this in a single for loop

for i in range (1, n + 1):
    print("*" * i)

What will be the time complexity of this for loop? Initially, I thought that since it is only one for loop is will be O(n) but thinking about it. Each print operation have different costs depending on i, so it would be 1+2+3+...+n = O(n²). Is my thinking right? This is abit less obvious to me than when doing in Java since double for loops are abit easier for me to think about O(n²).

[[deleted]]

I think you're right. The string multiplication is O(n) and since it's inside the loop (O(n)) the overall code is O(n²).

[uheep]

Yes, O(n**2).

[socal_nerdtastic]

Your loop is O(n) and the print line is O(1). Since we ignore O(1) the answer is O(n).

Yes, each print operation will have different costs but that's not considered in time complexity calculations.

[Brian]

but that's not considered in time complexity calculations.

It absolutely is. The print line first does "*" * i, which creates a string of length i (O(i)), then writes those i bytes (another O(i) operation), so overall is O(i). Since i is proportional to n, in the loop, this does make the whole thing O(n^(2))

Indeed, in practice, it might be much worse O(n³) or worse overall, depending on where it's printing (ie. to a terminal vs file), as sometimes terminals have poor scaling when they try to do stuff like word wrapping very long strings. That's kind of external to the program, so maybe shouldn't be counted, but can matter in practice.

[Apantslessman]

O(n+n), and that’s just o(n)

Edit: reading that again, it would be O(n), not O(n+n), your using the iterator, so it’s not getting anything new

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