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?