Describing the asymtotic complexity of processing two-dimensional data structures

Question

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.

Answer 1

The solution is that you shouldn't just ask whether it is "linear" -- ask what variable it is "linear" in.

Your example code has running time that is linear in the total length of the input strings. There's a long history of characterizing the running time of an algorithm as a function of the length of the input to the algorithm, and that's an entirely valid thing to do.

It's also true that its running time is $O(nk)$ where $n$ is the number of strings and $k$ is the length of the longest string. This might be a looser bound.

Both statements are true, and don't contradict each other. It's just a matter of identifying which upper bound on the running time is more useful.

Answer 2

You say it yourself: "this is a linear operation, since we iterate over every element/character once". Hence the complexity is $O(m)$, where $m$ denotes the total number of characters: this is linear in the number of characters.

It turns out that the gross estimate $m\le nk$ holds, hence the complexity is also $O(nk)$. This is linear in the product $nk$ (!) Rigorous wording could be "this is bilinear in $n$ and $k$", but this isn't used.

Now, if you freeze $n$ (actually bound it by a constant), the complexity reduces to $O(k)$, linear in the length of the longest string. And if you freeze $k$ (actually bound it by a constant), the complexity reduces to $O(n)$, linear in the number of strings. And if you freeze both, you get $O(1)$.

---

It could be more appropriate (and more accurate) to consider the average string length, let $\bar k$, with the obvious equality $m=n\bar k$.

Answer 3

As you say, this is a linear time function. Its running time is linear in the size of the input. Parametrizing the input in terms of the number of strings and the maximum length is suboptimal.

The solution using constant time len is better since it is linear in the number of strings rather than in the total input length, which could potentially (but not necessarily) be much larger.

A similar situation occurs in graph search algorithms, say DFS. You can state the complexity as $O(n^2)$, where $n$ is the number of vertices, or as $O(n + m)$, where $m$ is the number of edges. Since potentially $m \ll n^2$, we see that DFS is potentially much more efficient than some $\Theta(n^2)$ algorithm.

While the DFS example is artificial, exactly this situation occurs in linear algebra on sparse matrices, where naive algorithms run in $\Theta(n^2)$, and more sophisticated algorithms run in $O(n + m)$. For a dense matrix there is no difference, but for sparse matrices the latter are much faster.

Answer 4

This algorithm does not have linear complexity and as posed, provides (and uses) two separate variables, as you described n and k. From the candiates perspective, there is no indication that the list length or the string length is bounded in any manner.

Remember: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

I am going to ignore the n ≥ k for the rest of this argument.

What this means is that we are defining an upper bound to the complexity for f(n) (to less than g(n)) that can only grow as a scalar multiple of c in relation to the complexity of g(n).

In your example there are two variables so any attempt to define an upper bound based on one, can easily be violated by changing the other.

The inner loop is clearly bounded by the length of the longest string O(k) which is really saying there exists constants where 0 ≤ f(k) ≤ cg(k) for all k. However, that isn't the end of the problem, there is an arbitrary number of strings in the list that violates this. Simply speaking, if the list length is greater than c then the assertion 0 ≤ f(k) ≤ cg(k) becomes incorrect. The problem is that for any c provided, defining a list length of c+1 will cause this assertion to fail. (and changing c makes it no longer a constant).

The answer is O(n*k)