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
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(n2). 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
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
Of course, real-life cases are not so easy to solve, and sometimes an O(n2) 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!