The Importance of Being O(n)

Understaing complexity is very important, expecially in powerful languages like Ruby.

Take for example this implementation of a Deck class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Deck
  SUITES = ["C","D","H","S"]
  VALUES = ["2","3","4","5","6","7","8","9","10","J","Q","K","A"]

  attr_accessor :cards

  #YAY! fantastic O(N^2) initialization :-/ 
  def initialize
    @cards = []
    SUITES.each do |suite|
      VALUES.each do |value|
        @cards << "#{value}#{suite}"
      end
    end
  end
end

As you can see here, the code is correct, but very little efficient. To create the deck, we need to go 13 times for every element in the SUITES array.
13 * 4 = 52 iterations. The complexity is clearly O(n²). Since we are working with a little set of data, this may be negligible, but still, is there a better way to write this code?

Presenting the ImprovedDeck class!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class ImprovedDeck
  VALUES = ["2","3","4","5","6","7","8","9","10","J","Q","K","A"]

  attr_accessor :cards

  #YAY! Much better O(N) initialization :-D 
  def initialize
    @cards = []
    VALUES.each do |value|
      @cards << ["#{value}C","#{value}D","#{value}H","#{value}S"]
    end
    @cards.flatten!
  end

end

In the code above, we go through each element of the VALUES array only once, returning, in the end,the same deck as the first implementation. The tradeoff of this quickening is the face that we cannot input dynamically the SUITES inside the class, but this is not the case in which we have more than the regular set of suites.

Complexity now is O(n) , confirmed also by the following benchmarks:

1
2
3
4

(on running 1000 times the same method)
                   user     system      total         real
Deck           0.680000   0.020000   0.700000 (  0.703846)
Improved Deck  0.050000   0.000000   0.050000 (  0.047859)

Of course, real-life cases are not so easy to solve, and sometimes an O(n²) complexity is more than acceptable for a certain problem, but i think is a good practice to keep your mind open to further optimize your code.

PS: 1 bazillion thanks to Tim Ruffles for his help and constructive criticism. I wish all the critics was like yours!