Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
115 lines (82 sloc) 3.27 KB

Big-O Build Status

Big-O is a gem which analyse an anonymous function and verify that it follow a specific pattern in its memory usage or its execution time.


This gem has been tested on Mac OS X, using Ruby 1.9.3/1.9.2.


Installation is made through RubyGem:

gem install big-o


Directly in your code

Checking if a function has a complexity of O(n) is as simple as this:

require 'big-o'

time_complexity = BigO::TimeComplexity({
  :fn    => lambda { |n| do_something_time_consuming(n) },
  :level => lambda { |n| n }
time_complexity.process # => true if it is growing in time constantly.

It is also possible to define multiple configuration parameters:

require 'big-o'

time_complexity = BigO::SpaceComplexity({
  :fn => lambda { |n| do_something_time_consuming(n) }
  :level => lambda { |n| n },
  :range => 1..20,                # value of n
  :timeout => 10,                 # time in seconds
  :approximation => 0.05,         # percentage
  :error_pct => 0.05,             # percentage
  :minimum_result_set_size => 3,  # minimum results
  :after_hook => proc { },        # See before/after hooks
  :before_hook => proc { }

RSpec Matchers

If you are using RSpec, there is a matcher already defined for matching a complexity level:

require 'big-o'
require 'big-o-matchers'

describe 'do_something_time_consuming' do
  before :each do
    @time_complexity = BigO::TimeComplexity({
      :fn => lambda { |n| do_something_time_consuming(n) }

  it 'should have a complexity of O(n)' do
    @time_complexity.should match_complexity_level 'O(n)', lambda { |n| n }

  it 'should not have a complexity of O(1)' do
    @time_complexity.should_not match_complexity_level 'O(1)', lambda { |_| 1 }

The string used as the first parameter (e.g. 'O(n)') is used to describe the lambda given as the second parameter.

After/Before hooks

Your function depends on something which needs to run before every call of your function? You need to cleanup whatever dirty work your function performed? These operation are time consuming and they will affect the values of your function? Well, just throw these things in the before/after hooks!

time_complexity = BigO::TimeComplexity({
  :fn    => lambda { |_| whatever_action_which_doesnt_depend_on_n },
  :level => lambda { |n| n**2 },
  :before_hook => lambda { |n| prepare_fn_environment(n) },
  :after_hook => lambda { |n| clean_up(n) }
time_complexity.process # will only time :fn

Warning: The timeout is still in effect during before and after hooks execution (in our example, it may stop during clean_up). There should not be any sensitive code which needs to be executed in before/after hooks.

If you need to cleanup something after time_complexity.process, you will prefer to place this code out of :after_hook or :before_hook.

Change Log

  • SpaceComplexity has been removed. (> 0.1)


You may want to read more on the subject by reading:


Complexity is licensed under the MIT License - see the LICENSE file for details