Timeline for (operationalizable) Cost measure for small problems
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6, 2015 at 10:53 | history | edited | Martin Van der Linden | CC BY-SA 3.0 |
adapt question following comments
|
| Jun 6, 2015 at 7:23 | comment | added | Raphael | 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. | |
| Jun 6, 2015 at 5:59 | comment | added | David Richerby |
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.
|
|
| Jun 6, 2015 at 5:25 | answer | added | Qalnut | timeline score: 2 | |
| Jun 6, 2015 at 2:16 | comment | added | Martin Van der Linden | @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. | |
| Jun 6, 2015 at 2:10 | comment | added | D.W.♦ | 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... | |
| Jun 6, 2015 at 1:47 | history | edited | Martin Van der Linden | CC BY-SA 3.0 |
edited title
|
| Jun 6, 2015 at 1:46 | comment | added | Martin Van der Linden | Related questions : cs.stackexchange.com/questions/32114/…, cs.stackexchange.com/questions/19615/… | |
| Jun 6, 2015 at 1:34 | history | asked | Martin Van der Linden | CC BY-SA 3.0 |