Runtime of appending items from a 2d array to a 1d list

Question

Hello, can anyone help with the runtime/time complexity for appending all elements (using a nested loop) of a 2d array to a single list? I have been trying to find this everywhere but with very little luck

Answer 1

?? Your not allowed to use 'in'? You're using 'in' for your current version. Lol
Anyway, no it's not the most efficient, it's actually faster if you use the '+=' operator do to some internal optimizations of the python language.

for i in range(len(A)):
flat += A[i]

This also removes the need for the inner loop.

https://code.sololearn.com/cV5x8Emv55cr/?ref=app

Answer 2

Here's some info on time complexity. Your answer would depend on your code. Are you trying to flatten a list? Are you using your own algorithm to do so or using numpy/pandas? Are/Is the list(s) dimensional structure fixed and constant? (Always a list of flat lists), or is it unknown. Etc

https://www.sololearn.com/learn/6362/?ref=app

Answer 3

That would be O(n*m)
Where n is the length of the list A and m is the length of the inner list(s). It would be a close resemblance to O(n²).

FYI, you don't need to use range here since A and the inner lists are iterables.

for lst in A:
for element in lst:
flat.append(element)

Here's a couple of examples, one using itertools.

https://code.sololearn.com/cVahrjLtqevH/?ref=app
https://code.sololearn.com/cNdGsoa4gTvs/?ref=app

Answer 4

Not when used in this manner. Just run the code and check the output.

Answer 5

Oh wow

Answer 6

The time complexity (I'm guessing this is what you really mean, as runtime and TC aren't the same, but they are related) for flattening in this manner (keep in mind in won't work for more complex '3d' lists) is essentially O(n) where the time complexity of a typical mergesort is O(n log n).
The issue is that n changes from flattening to sorting.
For example if you used the matrix in my previous code, which is 5x5, (imagine it was unsorted though) for flattening n is equal to 5. Once flattened n is now 25 due to the original list having 5 lists with 5 elements each.

Answer 7

If n is the size of the original un-flattened list (5), Then I would say its O(n) + O(n*m log n*m), but this might just be a bit much for me to wrap my head around atm. Lol

Answer 8

Ha ha, thanks

Answer 9

Thank you. It would be something like this: def flat_matrix(A):
     flat = []
     for i in range(len(A)):
         for j in range(len(A[i])):
             flat.append(A[i][j])
     return flat

Answer 10

Thanks, we're not allowed to use 'in' for this class I'm doing unfortunately, or anything more advanced than len, range, append. Would you say the function I provide above is the most efficient way to append the elements of a 2d array into a 1d array, from a runtime perspective?

Answer 11

We can use for i in range, ha ha. Don't you need an inner loop to iterate over all the elements of the 2d array?

Answer 12

Sorry, one more question: if I do this and then do a mergesort on flat (the resulting list), what would the runtime be?

Answer 13

Ok, so if the matrix is symmetrical and the rows are sorted lists, with this flattening algorithm, would that plus merge sort be O(n log n) or O(n^2 log n)?