Big O runtime nested for loop and append

Big O runtime nested for loop and append - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Big O runtime nested for loop and append (/thread-39040.html)

Big O runtime nested for loop and append - yarinsh - Dec-23-2022

Hello, after an argumant I would like to get answer from people who know about that bigO

What is the runtime big O for this code?

I think this is n^2 but someone said its n^3 what is the big o for this code?

Thank you.

CODE:

BigO_2(n):
L = []
for i in range(n):
    for j in range(n):
        L.append(i*j)
for i in range(n):

IDK what is that VV

def [attachment=2162]

[attachment=2162]

RE: Big O runtime nested for loop and append - snippsat - Dec-23-2022

Post working code,now is very far from that.
To make it work and the last loop dos not make sense or work.

def BigO_2(n):
    L = []
    for i in range(n):
        for j in range(n):
            L.append(i * j)
    return L

result = BigO_2(10)

>>> len(result)
100

So for this code is the time complexity is O(n^2).
So it give 100 as input the len() should increase quadratic to 10000.

# result = BigO_2(100)
>>> len(result)
10000

Calculate n^2 in Python would be like this.

>>> 10 ** 2
100
>>> 100 ** 2
10000

RE: Big O runtime nested for loop and append - deanhystad - Dec-23-2022

If you really want to be a stickler, you could say is O(n^2 + n). Normally you don't worry about the O(n) part.

RE: Big O runtime nested for loop and append - Gribouillis - Dec-23-2022

(Dec-23-2022, 06:54 PM)deanhystad Wrote: If you really want to be a stickler, you could say is O(n^2 + n). Normally you don't worry about the O(n) part.

To be an even more stickler, O(n^2 + n) and O(n^2) are exactly the same thing mathematically speaking. There is no difference at all.

RE: Big O runtime nested for loop and append - stevendaprano - Dec-31-2022

The code you posted has a runtime of O(1) because it is a SyntaxError at compile-time, so there is no runtime behaviour Big Grin

list.append has amortised O(1) behaviour. Which means that if you start with a list and do lots and lots and lots of appends, on average each append will take the same amount of time. So we can treat the appends as a constant time operation, just like the i * j multiplication.

(Note: this is only true if i and j are relatively small, say less than 20 or 30 digits. For huge ints with hundreds of digits, multiplication takes time that depends on the number of digits.)

Your code loops N times for each value in range(N), so altogether it does N*N loops. That's quadratic O(N^2) behaviour, not cubic O(N^3).

Whoever told you this was cubic behaviour probably thinks that appending to a list is O(N). It isn't. However, inserting into the start or middle of a list can be. So if you change the code to do L.insert(0, i*j) instead of an append, you will probably see roughly cubic behaviour.