Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 25, 2012 #1
    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.
  2. jcsd
  3. Nov 25, 2012 #2
    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


    (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(2n) 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!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook