title: Project Euler #14: Why is my TreeMap algorithm slower than brute force?
body: <p>Background: I first learned C++ and Java in school a number of years ago, but I haven't done much programming over the past 9 or so years as my previous career did not require it.</p>
  
  <p>I decided to look into Project Euler to brush up on my programming and solved problem 14, which asks to find the integer between one and one million with the longest Collatz sequence. (The Collatz sequence proceeds by, given a starting number, multiplying the number by 3 and adding 1 if it's odd, or halving the number if it's even. The process continues until the number reaches 1.) </p>
  
  <p>I first solved the problem using brute force, as illustrated in the code below.</p>
  
  <pre><code>int n;
  long temp; // long is necessary since some Collatz sequences go outside scope of int
  int[] n_length = new int[1000000];
      for(n = 0; n &lt; 1000000; n++){
          temp = n + 1;
          n_length[n] = 1;
          while (temp &gt; 1){
              n_length[n]++;
              if (temp % 2 == 0) temp = temp/2;
              else temp = 3*temp + 1;
  
          }
      }
  int max = 0;
      int max_index = 0;
      for (int i = 0; i &lt; 1000000; i++){
          if (n_length[i] &gt; max){
              max = n_length[i];
              max_index = i;
          }
      }
      System.out.println("The number with the longest Collatz sequence is " + (max_index + 1));
  </code></pre>
  
  <p>I thought this approach would be inefficient, since it runs the algorithm significantly more often than necessary. Any number that is part of a previous number's Collatz sequence will effectively have its sequence determined already, and so you end up calculating the sequence of every single number every single time it comes up in a Collatz sequence.</p>
  
  <p>I decided it would be better to store each number in a map as soon as it comes up in a Collatz sequence, so you would only have to calculate it once. To do this, I used a TreeMap, with the numbers used as keys and the associate Collatz sequence length as the value, and used a recursive function to insert each number into the map as soon as it comes up in a Collatz sequence. (See the code below.)</p>
  
  <pre><code>public static TreeMap&lt;Long, Integer&gt; tm = new TreeMap&lt;Long, Integer&gt;();
  public static void main(String[] args) {
  
      tm.put((long)1, 1);
      int maxVal = 1;
      long keyWithMaxVal = 1;
      int maybeMax;
      for (long i = 2; i &lt;= 1000000; i++){
          if(!(tm.containsKey(i))){
              maybeMax = addKey(i);
              if (maybeMax &gt;= maxVal){
                  maxVal = maybeMax;
                  keyWithMaxVal = i;
              }
          }
      }
      System.out.println("The number with the longest Collatz sequence is " + keyWithMaxVal + " with length " + maxVal);
  }
  public static int addKey(long key){
  
      while (!(tm.containsKey(key))){
          if (key % 2 == 0){
              tm.put(key, 1 +addKey(key/2));
          }
          else{
              tm.put(key, 1 + addKey(3*key + 1));
          }
      }
      return tm.get(key);
  }
  </code></pre>
  
  <p>I used a TreeMap since it automatically sorts the keys on entry, so as I iterate through the for loop I can quickly check whether the keys have already been inserted and avoid calling the addKey method to add the keys unless I have to. I thought that this algorithm would be much, much faster.</p>
  
  <p>However, when I actually ran the code, I was surprised to find that the brute force algorithm came up with the answer instantaneously, while recursive TreeMap algorithm took much longer, around 6 seconds. When I modified my programs to go up to 5 million rather than one million, the difference became even more pronounced. I added some code to each program to make sure that the second program was doing less work than the first, and indeed I determined that the addKey method was only being called once for each key, while the number of times the while loop needed to iterate in the first program was equal to the sum of the lengths of all numbers Collatz sequences (i.e. much more often than the number of method calls in the second algorithm).</p>
  
  <p>So why is the first algorithm so much faster than the second? Is it because the array of primitives in the first algorithm requires fewer resources than the TreeMap of Wrapper objects in the second? Is searching the map to check if a key already exists slower than I anticipated (shouldn't it be log time?)? Are recursive methods that require large numbers of method calls inherently slower? Or is there something else I'm overlooking</p>