2
$\begingroup$

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. )

The professor, asked me a way to evaluate the performance of my algorithm (not the program), but my algorithm is simply a brute force of all the possible cases, and I don't think you can do any better without heuristics, therefore I think the questions makes no sense (at least to me).

Am I wrong?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Ask yourself the questions: How many possible cases are there? and How long does it take to try each case? $\endgroup$
    – Tom van der Zanden
    Commented Jan 18, 2015 at 15:59
  • 3
    $\begingroup$ OK, so you believe you can't do better. But how does that stop you evaluating the performance of the algorithm you actually have? It's like saying "My professor wants me to evaluate how long it will take to fly to Australia. But Australia is a really long way away and I don't think it's possible to get there faster than flying. So the question doesn't make sense." Of course it makes sense. $\endgroup$
    – David Richerby
    Commented Jan 18, 2015 at 18:06
  • $\begingroup$ Nono, maybe I was not clear enough. It's easy to state the asymptotic of the algorithm: (if I recall correctly) it should be O(Bell'sNumber(nodes)*edges*). Once we know this, the question remains: "is my algorithm good or bad?!" that's what puzzle me. $\endgroup$
    – asdf
    Commented Jan 19, 2015 at 17:44

3 Answers 3

Reset to default
4
$\begingroup$

There are plenty of ways to go about dealing with NP-hard problems.

Even if you know the asymptotic upper bounds on worst-case runtime (more you usually don't get), you don't have information about

  • the typical case and
  • the precision of your bound.

In the absence of exact analyses, all you can do is run the algorithm on a representative sample of inputs and compare it to others.

To be clear, even though your algorithm has bad $O$-runtime (in the worst case) it does not always take this long to finish. Go find out!

Conducting meaningful runtime experiments is not trivial, and often done horribly wrong in the literature. I can recommend (the affordable) A Guide to Experimental Algorithmics by C.C. McGeoch (2012) for an introduction.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That said, it's unlikely that brute force is better than at first glance. Try something smarter and you may be rewarded with better performance on chip if not on paper. (This happens; the most popular example is probably Simplex.) $\endgroup$
    – Raphael
    Commented Feb 18, 2015 at 8:24
6
$\begingroup$

It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.

Improve this answer
$\endgroup$
3
  • $\begingroup$ We already know the asymptotic for my algorithm. That's why I don't get the meaning of the question. $\endgroup$
    – asdf
    Commented Jan 19, 2015 at 17:44
  • $\begingroup$ @asdf "The problem is NP-complete" tells you that there's a nondeterministic algorithm that runs in polynomial time. But your algorithm is deterministic so the problem being in NP tells you nothing about the running time of your algorithm. $\endgroup$
    – David Richerby
    Commented Feb 18, 2015 at 8:19
  • $\begingroup$ @DavidRicherby A problem being in some complexity class does not tell you anything about any algorithm for it, ever. $\endgroup$
    – Raphael
    Commented Feb 18, 2015 at 15:57
0
$\begingroup$

Maybe your professor is asking you to implement and run your algorithm and evaluate the time it takes in different sizes of instances. As is brute force, maybe you can't go away to more than 20 vertices, but is still a good excercise.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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