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?
