Big O runtime nested for loop and append

[yarinsh]

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:

1 2 3 4 5 6

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

1 2 3

def <!-- start: postbit_attachments_thumbnails_thumbnail --> <a href="attachment.php?aid=2162" target="_blank"><img src="attachment.php?thumbnail=2162" class="attachment" alt="" title="" data-original-title="Filename: L2odR.jpg Size: 27.53 KB Dec-23-2022, 04:06 PM"></a>    <!-- end: postbit_attachments_thumbnails_thumbnail -->

   

[snippsat]

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

1 2 3 4 5 6 7 8

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)

1 2	>>> 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.

1 2 3

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

Calculate n^2 in Python would be like this.

1 2 3 4

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

[deanhystad]

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.

[Gribouillis]

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.

[stevendaprano]

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

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.