usernameson's blog

Question: How to determine complexity from running time on test case?
By usernameson, history, 8 years ago, In English

Has anyone looked into the problem of determining the algorithmic complexity of a solution to a problem using the maximum solving time on test cases of different sizes? I imagine you could use least squares where the basis functions include some polynomials, some powers of log, an exponential and products of these up to a certain fixed size. It might be an interesting thing to calculate for complex solutions.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The biggest problem that I can see here is I/O time. What I mean is that solution with only N in the input and the same complexity solution, but with array of N numbers will be quite different in their run time.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I might be missing something but won't these differences be taken into account by different constant terms? The way I am thinking such a program would output something like instead of leaving it in O form and you could compare the different coefficients of the terms in the I/O solution and the vector solution.

    → Reply