Problem size and how it's different than the input for an algorithm

Question

I am trying to understand how the input size, problem size and the asymptotic behavior of an arbitrary algorithm given in pseudo code format differ from each other. While I fully understand the input and the asymptotic behavior, I have problems understanding the problem size. To me it looks as if problem size = space complexity for a given problem. But I am not sure. I'd like to illustrate my confusion with the following example:

We have the following pseudo code:

ALGONE(x,y)
    if x=0 or x=y then
      return 1
   end
  return ALGONE(x-1,y-1) + ALGONE(x,y-1)

So let's say we give two inputs in $x$ and $y$ and $n$ represents the number of digits.

Since we are having addition as our main operation, and addition is an elementary operation, and for two numbers of $n$ digits, we need $n$ operations, then the asymptotic behavior is of the form $O(n)$.

But what about the problem size in this case. I don't understand what am I supposed to say. The term problem-size is so vague. It depends on the algorithm but even then, even if one is able to understand the algorithm what do you give as an answer?

I'd assume that in this particular case the problem size, might be the number of bits we need to represent the input. But this is a guess of mine, grounded in nothing.

Answer 1

I'm not sure what you mean by problem size, so let me give a few examples:

• We often analyze graph algorithms in terms of $|V|$ and $|E|$.
• We often analyze algorithms on arrays (sorting, binary search) in terms of $n$, the size of the array.
• We often analyze algorithms on square matrices in terms of $n$, the number of rows (or columns). Sometimes we often take the sparsity (number of non-zero entries) into account.

In this interpretation of problem size (which might differ from what you have in mind), we associate with each instance several parameters (often one, sometimes more) with respect to which we analyze the algorithm. It's up to us to define the problem size.

Input size is also not as clear cut as it might seem, for two main reasons:

• Sometimes we measures the input size in bits, but more often we measure it (implicitly) in terms of machine words (a machine word has length $O(\log N)$, where $N$ is the input size in bits). In specific areas such as computational geometry, we allow the words to have unbounded size.
• We don't usually have a specific encoding in mind. Usually all encodings have roughly the same size, but this is not always the case (for example, compare the adjacency matrix and adjacency list representations of graphs).

The concepts of input size and problem size are there to help us understand the complexity of algorithmic tasks. Use the definitions most appropriate for your application.

Answer 2

The asymptotic behavior can refer to any "measurand", such as the processor time taken, but also the space consumption, the number of comparisons, the number of SQL queries of whatever you want.

The input size indeed denotes the space taken by the input data (quite often written $n$, which can be itself an asymptotic representation). But $n$ can also be something different, such as the maximum value of an input parameter.

Problem size might refer to $n$, by language abuse.