I've never studied any computer science. So I've always passed over restricted-complexity questions, since I had no way of knowing the complexity of my code. Today, I decided to try and see whether I could change that. I read the tag description (as available on mobile, which I think is only the shorter part of it), which gave no info on how to find complexity, so Googled and found https://stackoverflow.com/q/9958299, which says there is no general way to find complexity. So how do I know the complexity of my code for a restricted-complexity question?
\$\begingroup\$
\$\endgroup\$
6
-
7\$\begingroup\$ Clarification: It's impossible to algorithmically find the complexity of an arbitrary piece of code. It's still definitely possible by hand. \$\endgroup\$– DJMcMayhem ModCommented Jul 4, 2018 at 17:17
-
\$\begingroup\$ @DJMcMayhem, what I wrote in the question is what I (perhaps wrongly) understood from SO, viz that there's no general method, i.e. one that works on every script. Are you saying something stronger, that there's no algorithm at all? But don't you use an algorithm when you check it by hand? \$\endgroup\$– msh210Commented Jul 4, 2018 at 23:57
-
\$\begingroup\$ You have to study computer science and prove that your algorithm has the claimed complexity, of course. If you get it wrong, don't worry, we can <s>help</s> point out your mistakes. \$\endgroup\$– user202729Commented Jul 5, 2018 at 3:17
-
1\$\begingroup\$ Note that, in questionable cases, we require the answer poster to prove that their answer is valid, not vice versa. \$\endgroup\$– user202729Commented Jul 5, 2018 at 3:19
-
3\$\begingroup\$ About "but don't you use an algorithm when you check it by hand": Think about it like solving a math problem. There are no general algorithm that can solve all math problems, and some problems are unsolvable. (and there are automatic provers that can solve some problems) \$\endgroup\$– user202729Commented Jul 5, 2018 at 3:21
-
\$\begingroup\$ Related. \$\endgroup\$– msh210Commented Jul 16, 2018 at 11:39
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
2
Ask in chat
Your best bet is to ask someone else. Learning to evaluate the asymptotic complexity of a program is a pretty standard subject in most college CS educations, so there will probably be a number of people in chat who can either walk you through evaluating the complexity or do it for you, although the latter may be more difficult if you're using an esoteric language.
For most small (<100 lines in a conventional language) programs, it's pretty easy to evaluate the complexity with some practice, so someone can often walk you through it.
As an aside, evaluating complexity automatically is an ongoing research question in the programming languages world. I know some people who are working on it at my university. The best efforts cover a fair number of cases, but aren't all that general, and require you to write your program in their language. For the time being, human evaluation is typically the most effective.
-
\$\begingroup\$ Thanks. This works if people are willing to help me — a lot. I mean, it would (at first) take the form of "What's this script's complexity?" (An answer.) "Okay, so what's this one's?" … Quite a bit of time and effort expended by the helpers. \$\endgroup\$– msh210Commented Jul 11, 2018 at 4:53
-
\$\begingroup\$ @msh210 I'm thinking you might want to ask "How do I figure out this script's complexity", and then someone might walk you through the answer, so you can figure it out yourself if you make a small change \$\endgroup\$– isaacgCommented Jul 11, 2018 at 4:55