title: Why the maxmin divide and conquer implementation is slower than the others maxmin algorithms?
body: <p>I'm comparing the complexity about the implementation of the maxmin algorithm and I have implemented in two ways: the brute force way and the divide and conquer way. After I tested both two algorithms for ten input of elements between 1000000 and 10000000. Follow below the algorithms:</p>
  
  <p>The brute force implementation below:</p>
  
  <pre><code>def maxmin1(vetor):
      max,min = vetor[0],vetor[0];
      for elem in vetor[1:]:
          if elem &gt; max:
              max = elem
          if elem &lt; min:
              min = elem
      return (min,max)
  </code></pre>
  
  <p>and divide and conquer implementation below:</p>
  
  <pre><code>def maxmin4(vetor,inicio,fim):
      if ((fim - inicio) == 1):
          return (vetor[inicio], vetor[inicio])
      elif ((fim - inicio) == 2):
          if( vetor[inicio] &lt; vetor[inicio+1]):
              return (vetor[inicio], vetor[inicio+1])
          else:
              return (vetor[inicio+1], vetor[inicio])
      else:
          (min_left,max_left) = maxmin4(vetor,inicio,(fim-inicio)/2 + inicio)
          (min_right,max_right) = maxmin4(vetor,(fim-inicio)/2 + inicio,fim)
          if (max_left &lt; max_right):
              max = max_right
          else:
              max = max_left
          if (min_left &lt; min_right):
              min = min_left
          else:
              min = min_right
      return (min,max)
  </code></pre>
  
  <p>and the results:</p>
  
  <pre><code>input N     time algorithm 1 |  time algorithm 2
  1000000 |   0.1299650669     |  0.6347620487 
  2000000 |   0.266600132      |  1.3034451008
  3000000 |   0.393116951      |  2.2436430454
  4000000 |   0.5371210575     |  2.5098109245
  5000000 |   0.6094739437     |  3.4496300221
  6000000 |   0.8271648884     |  4.6163318157
  7000000 |   1.0598180294     |  4.8950240612 
  8000000 |   1.053456068      |  5.1900761128
  9000000 |   1.1843969822     |  5.6422820091
  10000000|   1.361964941      |  6.9290060997
  </code></pre>
  
  <p>I don't understand why the first algorithm was faster than the second, since the first have the complexity 2(n -1) and the second have complexity 3n/2 -2 and in theory the first is slower than the second. why it happens?</p>