0

If I have a question that I need to append a copy of list2 of size n to the end of list1 n times, is the time complexity O(n) or O(n^2)? Code is below.

for i in range(n):
    list1.append(list2)

What if I append a copy of list2?

for i in range(n):
    list1.append(list2[:])
Blake Han
  • 11
  • 3
  • *"wouldn't the time complexity be equal to the size of the list?"* -- Why would that be? Are you thinking Python copies on assignment? **Edit**: Oh wait, when you say "size of the list", which list are you referring to? – wjandrea Jun 04 '22 at 01:16
  • 2
    Do you mean `list1.extend(list2)`? `append` adds a single item to `list1`. `extend` adds many items. – John Kugelman Jun 04 '22 at 01:23
  • Are you aware that that first snippet never creates a copy? – wjandrea Jun 04 '22 at 01:28
  • @KarlKnechtel [Why is the time complexity of python's list.append() method O(1)?](https://stackoverflow.com/questions/33044883/why-is-the-time-complexity-of-pythons-list-append-method-o1) is a better duplicate than the [linked one](https://stackoverflow.com/questions/70529063/what-is-the-time-complexity-for-appending-an-element-to-a-list), although I'm not certain this is a duplicate of either. – John Kugelman Jun 04 '22 at 01:29
  • Appending a single element (even if it's a list) to a list is amortized O(1). Nothing needs to be copied; lists contain references (which is why they're able to store any kind of object). Even if the storage is resized, O(1) elements are copied on average because the storage space is grown exponentially. Copying a list is O(n) in the size of that list, so appending a copy is, too. Repeating a process n times explicitly, adds a factor of n to big-O running time. – Karl Knechtel Jun 04 '22 at 01:29
  • @JohnKugelman you have a gold badge in the Python tag, right? Feel free to overrule me here. – Karl Knechtel Jun 04 '22 at 01:30
  • You could be right, I'm not sure, so not overruling. – John Kugelman Jun 04 '22 at 01:31

0 Answers0