# Big-O of iterating through nested structure

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?

• Those are two different choices of variables measuring the size of the input. It is fine, as long as you say what is each variable in each case. – plop Sep 11 '20 at 14:14
• is O(n * m) only correct answer? to most questions, it isn't even correct: I prefer an explicit question in the question body (over one to be deduced from the title). – greybeard Sep 11 '20 at 16:24
• A better bound on the complexity is linear in the number of files. – Yuval Filmus Sep 11 '20 at 19:31

A better bound on the complexity is $$O(k)$$, where $$k$$ is the total number of files.