As we have seen previously, algorithms that have an exponential runtime complexity scale really poorly. There are many examples of problems for which only an O(kⁿ) solution is known. Improving these algorithms is a very dynamic area of study in computer science. Examples of these include the traveling salesman problem and cracking a password using a brute force approach. Now, let's see an example of such problem.

A prime number is only divisible by itself and one. The example problem we present here is called the prime factorization problem. It turns out that if you have the right set of prime numbers, you can create any other possible number by multiplying them all together. The problem is to find out these prime numbers. More specifically, given an integer input, find all the prime numbers that are factors of the input (primes that when multiplied together give us the input).

Snippet 1.8 shows one implementation for this problem, called trail division. If we take an input decimal number of n digits, this algorithm would perform in O(10ⁿ) in the worst case. The algorithm works by using a counter (called factor in Snippet 1.8) starting at two and checks whether if it's a factor of the input. This check is done by using the modulus operator. If the modulus operation leaves no remainder, then the value of the counter is a factor and is added to the factor list. The input is then divided by this factor. If the counter is not a factor (the mod operation leaves a remainder), then the counter is incremented by one. This continues until x is reduced to one. This is demonstrated by the following code snippet:

public List<Long> primeFactors(long x) {
  ArrayList<Long> result = new ArrayList<>();
  long factor = 2;
  while (x > 1) {
    if (x % factor == 0) {
      result.add(factor);
      x /= factor;
    } else {
      factor += 1;
    }
  }
  return result;
}  

Try executing the preceding code for the following two numbers:

• 2100078578
• 2100078577

Why does it take so long when you try the second number? What type of input triggers the worst-case runtime of this code?

The worst case of the algorithm is when the input is a prime number, wherein it needs to sequentially count all the way up to the prime number. This is what happens in the second input.

On the other hand, the largest prime factor for the first input is only 10,973, so the algorithm only needs to count up to this, which it can do quickly.

Exponential complexity algorithms are usually best avoided, and an alternate solution should be investigated. This is due to its really bad scaling with the input size. This is not to say that these types of algorithms are useless. They may be suitable if the input size is small enough or if it's guaranteed not to hit the worst case.