title: Running time Array#unshift vs Array#shift
body: <p>I expected the running time of <code>Array#shift</code> and <code>Array#unshift</code> both to be <code>Θ(n)</code>. Reason being that the machine needs to loop through each array member and assign it to the key left or right to it.</p>
  
  <p>In the case of <code>Array#unshift</code>, assuming that only one value is passed in as an argument and that there are lots of array members, I assumed that the value assignment for <code>array[0]</code> is not having a significant impact on the running time. In other words, when the number of array members is high and the number of variables passed into <code>Array#unshift</code> is low, I expected <code>Array#shift</code> and <code>Array#unshift</code> to have the same running time.</p>
  
  <p>When running benchmarks on Ruby 2.1.2, these assumptions do not hold true. Why?</p>
  
  <p>Code:</p>
  
  <pre><code>require 'benchmark'
  
  GC.disable    
  
  number_of_elements = 25_600_000
  
  a1 =[]
  a2 = []
  a3 = []
  a4 = []
  q1 = Queue.new
  q2 = Queue.new
  
  puts number_of_elements
  
  number_of_elements.times do
    q1.enq(true)
    q2.enq(true)
    a1 &lt;&lt; true
    a2 &lt;&lt; true
    a3 &lt;&lt; true
    a4 &lt;&lt; true
  end
  
  number_of_operations = 1
  
  Benchmark.bm do |bm|
    puts "Queue#enq('test')"
    bm.report do    
      number_of_operations.times { q1.enq('test') }
    end
  
    puts "Queue#deq"
    bm.report do    
      number_of_operations.times { q2.deq }
    end
  
    puts "Array#shift"
    bm.report do
      number_of_operations.times { a1.shift }
    end 
  
    puts "Array#unshift"
    bm.report do
      number_of_operations.times { a2.unshift('test') }    
    end 
  
    puts "Array#pop"
    bm.report do
      number_of_operations.times { a3.pop }
    end
  
    puts "Array#&lt;&lt;"
    bm.report do
      number_of_operations.times { a4 &lt;&lt; 'test' }
    end      
  end
  </code></pre>
  
  <p>Result:</p>
  
  <pre><code>25600000
         user     system      total        real
  Queue#enq('test')
     0.000000   0.000000   0.000000 (  0.000006)
  Queue#deq
     0.010000   0.020000   0.030000 (  0.029928)
  Array#shift
     0.010000   0.020000   0.030000 (  0.032203)
  Array#unshift
     0.080000   0.060000   0.140000 (  0.143272)
  Array#pop
     0.000000   0.000000   0.000000 (  0.000004)
  Array#&lt;&lt;
     0.000000   0.000000   0.000000 (  0.000007)
  </code></pre>