Consider the following Python function:
def count_chars(list_of_strings):
chars = 0
for s in list_of_strings:
for c in s: # intentionally avoiding len() here for the sake of example
chars += 1;
return chars
Clearly this is a linear operation, since we iterate over every element/character once. But I've often seen the Big-O of this function as $O(n*k)$ where $n$ is the length of the list, and $k$ is the length of the longest string. In a sense, that's polynomial or quadratic (at a minimum, I've heard people refer to this type of algorithm as such).
What is the appropriate way to refer to this type of function? Is there an intuitive way to understand this is linear, despite multiple variables? In particular, how can we discuss that this is worse than a solution that uses len()
(which is $O(1)$) without getting hung up on the fact that, in practice, both are linear?
Context: I'm posing an interview question that, while more complex than this example, involves identifying and eliminating $k$. I've had candidates struggle to see that and it's felt like a communication issue more than a understanding problem.
I'm looking for ways to help guide a discussion, and to recognize that while this is linear, it is still asymptotically worse than an operation that avoids hitting each character individually.