# How should I express the complexity of two nested loops over different datasets in Big O notation?

I'm more or less teaching myself big O notation, so please forgive me if this is a duplicate of a question which applied to my question without me having the wisdom to realise it. For my own amusement/personal development, I'm trying to express the complexity of a function which works on 2 different datasets which relate to each other: I need to iterate over a list, and for each item in a list, iterate over another list checking if the items are related.

Pseudocode:

``````for things in list_a {
for things in list_b {
if (list_a.thing relates to list_b.thing) go ping
}
}
``````

What I have on paper currently is O(n) * O(m), but I'm wondering if it should be expressed as O(n*m) instead, where n = size of set b and m = size of set a? Or is this something else entirely? Again, apologies if this is a stupid/duplicate question, but I couldn't find anyone specifically discussing a nested loop over two different datasets. This answer would suggest that it's O(n^2), but that feels wrong to me, since the sizes of the two datasets themselves are different and independent.

It'd be O(n`*`m) where the worst case is n = m or n*n thus O(n^2). We are interested in worst case run time for Big O. If the data sets sizes are different then it will still be in O(n^2) since we can't guarantee that, for example, the second dataset will be a logarithmic relation to the first. If we could, they wouldn't necessarily be independent. They might be but again, we are looking at worst case and O(nlogn) is within O(n^2).
• Why is the reduction from O(`n*m`) to O(n^2) valid? You lose the important information that the complexity depends on two independent inputs. – Bart van Ingen Schenau Feb 8 '16 at 7:35