Does this program have a runtime of O(N) or O(n*m)

Question

This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure I am properly evaluating the run time of this algorithm.

Imagine we have a list of strings, such as this:

words = ["eat", "tea", "tan", "nat", "bat", "cat", "act"]

We want to visit each character of each word in this list (The above example comes from an anagram grouping prompt). What would the runtime of visiting each character be? Assume that neither the number of words or the length of the words are constants. They are both variables.

in python, that could be done as so

for w in words:
    for c in w:
        print(c)

I have seen the run time of visiting every element in this list as being:

O(n*m): where n is the number of words in the list and m is the number of characters

O(N): where N is the total number of characters in the list

O(N) is clearly linear, but O(n*m) is not (according to the answers in the aforementioned question)

How can the same algorithm be both linear and not linear, simply depending on how you describe the inputs.

In the example case I am considering, all words have the same number of characters, but how might our answer change if this was not the case? Does m then represent the average character length? the length of the longest word?

Answer 1

Big $O$ is merely a function that describes an upper bound of another function, so it can be used in different ways. You can describe the big $O$ of the memory usage of a function, or the big $O$ of the number of operations a function performs.

What you've encountered is simply that, by using different descriptors of the inputs, you wind up with different descriptors of the function itself. The function you have described is, in fact, linear to the total number of characters in the input. That statement is not wrong, but $O(nm)$, where $m$ is the average number of characters of the words in a set, is clearly a more useful description of the behavior of the function.