On each iteration of the loop, the length of l1 grows by the length of l2. With the first version, each of those iterations copies every element in each list, s

On each iteration of the loop, the length of l1 grows by the length of l2. With the first version, each of those iterations copies every element in each list, so you end up copying the same elements many times. The arithmetic gets slightly obscured in this example because both lists have length 1 to start with. Let’s instead call the initial list lengths L₁ and L₂. On the first iteration of the loop, we need to copy L₁ + L₂ elements to build the concatenated list. However, on the second iteration, the length of l1 is now L₁ + L₂, so we need to copy (L₁ + L₂) + L₂ = L₁ + 2L₂ elements. On subsequent iterations, we then need to copy L₁ + 3L₂ elements, then L₁ + 4L₂, etc. If we are running the loop N times (in this example, N = 10⁵) then we end up copying the original elements from l1 N times, but the original elements from l2 get copied 1 + 2 + … + N = N(N+1)/2 times. So the total number of element copies made during the entire run of the loop is NL₁ + ((N²+N)/2)L₂. With big-O, we need the term that grows fastest and conventionally we write it ignoring any constant scale factors. In this case, that term is the N² because everything else only grows as fast as N, so we say the algorithm is O(N²). As an aside, for the same conventional reason, we would normally say the second version is O(N). It’s not technically incorrect to say it’s O(2N) according to the definition of big-O, but it’s not idiomatic.