I have a list of list, in different length, and my algorithm runs on every element in the sub lists.

What should be my time complexity?

I don't know if it's okay to write O(n * m), as n length of parent list and m is the average length of t E sub lists, or maybe O(n) as n is the number of total elements.

Please explain what the meaning of the symbols (for example n is the length of the parent list).

CodePudding user response：

If you have n sublists with m elements each, n*m represents the total number of elements being processed, hence it has a complexity of O(n*m).

If your sublists have an unequal number of elements, it is okay to summarise it as O(N), where N is the total number of elements in the array.

CodePudding user response：

You get to define your variables, so it is perfectly fine to say "O(n) where n is the size of the input".

Your case seems similar to "sparse" matrix methods: sparse matrices have a well-defined width and height, as well as a total size (of non-zero elements). Algorithm performance descriptions can use all three parameters as appropriate.

Ultimately, it should be about what is convenient for describing the algorithm.

CodePudding user response：

You are carrying out an operation N total times. So unless your algorithm accesses some of these other elements inside it, that makes it an O(N) operation. The act of transitioning from one sublist to the next, even if it takes an appreciable time, is an O(m) operation. But since m is less than N, you can ignore it because as N becomes very large it overwhelms the O(m) timing. Indeed, the whole purpose of the 'Order of' analysis is to demonstrate an algorithm's responsiveness under extreme conditions.