It’s not n^2, it only iterates over the list or lists sequentially. You would have to visit items more than once to get n^2. I’m not denying that it’s worse and

It’s not n^2, it only iterates over the list or lists sequentially. You would have to visit items more than once to get n^2. I’m not denying that it’s worse and it’s a excellent point, just that it’s only unfortunate not exponentially unfortunate. (Edit) leaving the comment for integrity of the thread but I failed to notice that you absolutely revisit the first elements of the first array every time through the loop (which is growing in size), which absolutely makes it n^2 whereas the better version just tacks it on without reconstruction.