What does "algorithm problem size" actually mean?

user_8152101 0
Viewed 1206

I'm currently in a Data Structures course at my university and did do some algorithm analysis in a prior class, but it was the section I had the most difficult time with in the previous course. We are now going over algorithm analysis in my data structures course and so I'm going back through my textbook from the previous course to see what it says on the matter.

In the textbook, it says "For every algorithm we want to analyze, we need to define the size of the prob- lem." Doing some Google searching, it's not entirely clear what "problem size" actually means. I'm trying to get a more concrete definition of what a problem size is so I can identify it in an algorithm.

I know that, if I have an algorithm that is sorting a list of numbers, the problem size is n, the size of the list. With that said, saying that doesn't clarify what "problem size" actually is, except for in that context. An algorithm is not just a process to sort numbers, so I can't always say that the problem size is the number of elements in a list.

Hoping someone out there can clarify things for me, and that you all are doing well.

Thank you

algorithm
3 Answers

The answer is right there in the part you quoted (emphasis mine):

For every algorithm we want to analyze, we need to define the size of the problem

The "problem size" is only defined numerically relative to the algorithm. For an algorithm where the input is an array or a list, the problem size is typically measured by its length; for a graph algorithm, the problem size is typically measured by the number of vertices and the number of edges (with two variables); for an algorithm where the input is a single number, the problem size may be measured by the number itself, or the amount of bits required to represent the number in binary, depending on context.

So the meaning of "problem size" is specific to the problem that the algorithm solves. If you want a more universal definition which could apply to all problems, then the problem size can be defined as the number of bits required to represent the input; but this definition is not practical, and is only used in theory to talk about classes of problems (such as those which are solvable in polynomial time).

user_122990000

The problem size is the number of bits needed to store an instance of the problem, when it is specified in a reasonable encoding.

user_32554550

To clarify the concept, let me define this in the layman's terms:

Given:

  • You have a big phone book.

Problem:

  • You are told to find the number of person John Mcallister.

Approach:

  • You can either search for this entry through each page (in the linear manner);
  • or, if the phone-book is sorted, you can utilize Binary Search;

Answer to your question:

  • Algorithm problem here is Finding the entry in the Phone Book;
  • Algorithm problem's size is the size of data, your algorithm should apply to (in your case, it's the size of your phone-book. If it has 10 entries per each page, and the book has 50 pages, the size is 50x10=500, to wit, 500 entries.)
  • As your algorithm should solve your task of examining entire phone book, the size of your task/problem, which you implement the algorithm for, is 500.

Problem Size is generally denoted with n and it literally means the size of input data.

user_15535370
Related