Trying to come up with simple algorithm of significant time complexity in Java

[frankfjf]

Hi PF,

I'm working on a program that requires measuring how long it takes a given computer to process a certain task, but am having trouble coming up with algorithms that won't take most computers a trivial amount of time to perform. The only one I've got so far is recursively computing Fibonacci numbers.

Can anyone suggest similarly simple methods that will tie up a computer for more than an instant? It's fine if the method only slows things down for large inputs.

 

[Adyssa]

You need an NP problem! Here's a list of some good hard (for a computer) algorithms. Last year I implemented a 3SAT-Solver and brought my computer to it's knees. It wasn't too hard. A 3SAT problem is a boolean satisfiability problem, given a conjunction of clauses

i.e.

(a OR b OR ~c) AND (b OR c OR ~d) AND (...) AND (...) etc

What is an assignment you can give to a, b, c, d, etc that will make the expression evaluate to true?

The traveling salesman problem is another famous one. Given a set of cities with some cost between each one, what is the route that visits all cities once (hamiltonian path) with the least cost. You can represent the cities and connecting paths with a graph and write a graph traversal algorithm to find hamiltonian paths, which is computationally costly in the first place, and you need to find every possible hamiltonian path before you can be sure that you have the one with least overall cost.

These problems have time complexity of O(2ⁿ) where n is the size of the input, so you can see that as soon as n gets even remotely big, the time it takes to solve these problems gets very, very, very, very, very big!