4
\$\begingroup\$

I've never studied any computer science. So I've always passed over 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?

| |
\$\endgroup\$
  • 6
    \$\begingroup\$ Clarification: It's impossible to algorithmically find the complexity of an arbitrary piece of code. It's still definitely possible by hand. \$\endgroup\$ – James Jul 4 '18 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\$ – msh210 Jul 4 '18 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\$ – user202729 Jul 5 '18 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\$ – user202729 Jul 5 '18 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\$ – user202729 Jul 5 '18 at 3:21
  • \$\begingroup\$ Related. \$\endgroup\$ – msh210 Jul 16 '18 at 11:39
4
\$\begingroup\$

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.

| |
\$\endgroup\$
  • \$\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\$ – msh210 Jul 11 '18 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\$ – isaacg Jul 11 '18 at 4:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .