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
  • 19
  • 5
  • *"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
  • 1
    @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
  • Appending ONE item to a list is `O(1)` for sure but as @KarlKnechtel mentioned, appending a copy to a list is `O(n)`. Why is this closed though? It is a pretty reasonable question and in a loop, it is a factor of how many times that loop goes through. – ARAT Sep 02 '22 at 12:39
  • "It is a pretty reasonable question" Why? What actually is the conceptual difficulty here? If it is "given that a loop runs N times and does an O(1)/O(N) thing each time, *how do we determine* that this is O(N)/O(N^2)?", then I don't understand how the question can be asked - this is always explained simultaneously with *what the big-O notation means in the first place*. If it is "why does it take at least O(N) time to copy something with N elements?" then I can't fathom the reasoning behind supposing that it could be done faster. And OP already knows that the second example makes a copy. – Karl Knechtel Sep 02 '22 at 23:39
  • @ARAT (2/2) So either there is a simple logical error (equivalent to a typo); a refusal to consider the problem entirely; or else the only remaining issue I can see is "does `list.append` copy what it's appending?" and the answer is no and this is common duplicate material. If it was caused by confusing `.append` with `.extend` (i.e., expecting O(N) elements to be appended separately, rather than the list being treated as a single item), that is *also* common duplicate material. In no case is this a question that should remain open. – Karl Knechtel Sep 02 '22 at 23:40

0 Answers0