# (operationalizable) Cost measure for small problems

For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they would all be solved in about the same time.

Yet, I turn out to be interested in some cost measures for small problems. For instance, although both 12 + 14 and 123503 + 589034 can be solved in the blink of an eye by today's computers, there seems to be a sense in which 123503 + 589034 is still more "costly" than 12 + 14.

So my question is : do you know of any such cost measures that would be appropriate for such small size problems?

Note 1 : I am interested in rather general answer for all kinds of problems, the addition one being just an example.

Note 2 : the best I have found so far is Kolmogorov's complexity, but for what I understand of it, it seems awfully hard to operationalize. First it appears to be dependent on the reference language, and second, once a language is chosen, it seems really hard to prove that a description of a string is of minimal length.

• Do you know of any measure which would be easier to implement?
• Am I missing something about Kolmogorov's complexity and is it easier to implement than I suggest?
• Related questions : cs.stackexchange.com/questions/32114/…, cs.stackexchange.com/questions/19615/… – Martin Van der Linden Jun 6 '15 at 1:46
• The first step is to figure out what you're trying to measure. What do you mean by complexity? What do you mean by small? What do you want to do with it? Before you can design or select a metric, you first need to know what you're trying to measure... – D.W. Jun 6 '15 at 2:10
• @D.W. : At this point, I am not sure I can give a good answer to your questions. I understand that it would make the question much better and much easier to answer. But I don't have anything more precise in mind that what I wrote. Sorry if it makes the question too vague, feel free to vote to close if you feel like it cannot be answered in its current state. – Martin Van der Linden Jun 6 '15 at 2:16
• Complexity theory deals with problems, whereas you're talking about properties of individual instances. It's not clear what that means, since any individual instance can be solved in linear time. For example, sum (x,y) { If (x=123503 and y=589034) return 712537; else return x+y; } Complexity has to be over a class of instances. – David Richerby Jun 6 '15 at 5:59
• Get rid of the term "complexity" and use "cost measure". Then, analyse the algorithm rigorously w.r.t. this cost measure. If you get an exact result like "A needs $17n + 5$ arithmetic operations on input $n$", great. Often you won't, and that's why we use asymptotics -- the calculations are more manageable. – Raphael Jun 6 '15 at 7:23