While trying to understand complexity I run into an example of going through records organized in following way:
data = [ {"name": "category1", "files": [{"name": "file1"}, {"name": "file2"}], {"name": "category2", "files": [{"name": "file3"}] ]
The task requires to go through all file records which is straight forward:
for category in data: for file in category["files"]: pass
It seems like complexity of this algorithm is O(n * m), where n
is length of data
and m
is max length of files
array in any of data
records. But is O(n * m) only correct answer?
Because even there are two for-loops it still looks like iterating over a global array of file records organized in nested way. Is it legit to compare with iteration over different structure like that:
data = [ ('category1', 'file1'), ('category1', 'file2'), ('category2', 'file3'), ] for category, file in data: pass
…where complexity is obviously O(n), and n
is a total number of records?