11

I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's taking way too much time to do it by hand. it's also prone to human errors.

I spent some time on Codility (coding/algo exercises), and noticed they will give you the Landau notation for your submitted solution (both in Time and Memory usage).

I was wondering how they do that... How would you do it?

Is there another way besides Lexical Analysis or parsing of the code?

This question concerns mainly PHP and or JavaScript, but I'm opened to any language and theory.

Improve this question
3
  • 4
    Check this answer from SO. It sounds like what you're looking for.
    – Deco
    Sep 7, 2012 at 3:44
  • 2
    If you can create a program that solves this problem for each and every algorithm, you will become famous as "the man who disproved Turing".
    – user281377
    Sep 7, 2012 at 11:52
  • 1
    For proofs that deciding running times is in general impossible, see here and here - the answers there prove even more than you ask for, actually.
    – Alex ten Brink
    Oct 2, 2012 at 13:46

5 Answers 5

Reset to default
13

I was wondering how they do that... How would you do it?

I imagine that they are actually estimating the Big O measures ... by running the program for different problem sizes, measuring time and space usage, and fitting curves to the results.

The problem with this approach is that it can get it wrong if the cost functions change shape as N gets large; e.g. 1000 N + N^1.5.

Is there another way besides Lexical Analysis or parsing of the code?

Lexical analysis and parsing are not sufficient. You also need to do some reasoning about the behaviour of the algorithm. And doing that automatically for a previously unknown algorithm is hard.

Improve this answer
4
  • 6
    "doing that automatically for a previously unknown algorithm is hard" – More precisely: it is equivalent to solving the Halting Problem.
    – Jörg W Mittag
    Sep 7, 2012 at 9:40
  • Ermm ... not exactly. Solving the Halting Problem would be equivalent to being able to do it for all previously unknown algorithms.
    – Stephen C
    Sep 7, 2012 at 12:21
  • 2
    Yes, sorry. Doing it for one algorithm is equivalent to (or rather implies) proving termination.
    – Jörg W Mittag
    Sep 7, 2012 at 18:11
  • 1
    The practicalities of this are that 1) it is impossible to prove or disprove termination for some algorithms, but 2) most algorithms don't have this theoretical impediment, but 3) the state of the art in theorem proving is not far enough advanced to be able to do this anyway ... except in relatively simple cases. Hence my statement that I imagine they are doing this a different way. But obviously, we cannot be sure how they are really doing this without looking at their code.
    – Stephen C
    Sep 9, 2012 at 4:14
3

They can't without analysing the code.

Below examples with artificial "inflation / deflation" of complexity proves that simply measuring program runtime is not sufficient to reliably estimate Big-O

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

Runtime estimation for above would be succeptible to giving fake estimates - constant time for values of n where there is a pre-calculated solution and cubic time for values where unfair slow-down kicks in - instead of "fair" quadratic time.

Improve this answer
1
  • However, if they do happen to check the "unfair" cases, they can still assume that the worst case indeed estimates the Big-O complexity.
    – Yam Marcovic
    Oct 2, 2012 at 6:54
1

I think that this is not possible.

If you run some tests with a fixed number of different input sizes, you can easily compute a polynomial, that will approximate the runtimes you have measured very good. So you end up with a polynomial for every possible program, which would mean P = NP (yeah! ;) ).

If you try to do it with symbolic manipulation, you end up at the halting problem. Since you can't decide wether your program will ever stop, you can't decide what runtime complexity it will have.

There may however be very special cases, where the later method is possible. But these cases maybe that small, that it's questionable if effort ever gets paid.

Improve this answer
1
  • 1
    +1, although I think that the halting problem could be considered a rarity.
    – Yam Marcovic
    Oct 2, 2012 at 6:59
0

How would I do it? The way I solve almost any problem I don't want to sit down and solve. I simulate.

For many problems, it may be sufficient to run your algorithm many times using a variety of sizes, and then fit a regression curve to those results. That would quickly identify some particular "fixed" overhead costs of your algorithm (the intercept of the curve) and how it scales as your problem size increases.

Some tinkering will be needed to capture particularly complicated solutions, but especially if you're just looking for a ball-park estimate, you should be able to obtain it that way, and see how your estimate differs from your actual results and decide if it's an acceptable approximation.

The greatest weakness in my mind with this method is that if your algorithm scales really poorly, that initial "run it a whole bunch of times" step is going to get ugly. But frankly, it thats the case, that alone should be an indicator that you might want to step back and reconsider things.

Improve this answer
0

My intuition is that a general solution to this problem is impossible; asserting, as it does, a priori facts about the runtime of algorithms without running them (you allude to lexical analysis). That said, it is possible for some heuristic algorithm for a (probably large) class of algorithms (since we do it all the time), but a general algorithm to do this would be equivalent to solving the Entscheidungsproblem which is well known not to be possible (cf. Church, Turing, et al.). I’m ~99.9% sure of this now that I think about it…

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.