plasma-umass/bigO

Measures empirical computational complexity (in both time and space) of functions

bigO

bigO automatically measures empirical computational complexity (in both time and space) of functions. To use bigO, you just need to add a @bigO.track decorator to your function together with a "length" function (the "n"). You can then run your function as usual, ideally along a wide range of inputs, and bigO will report the computational complexity of that function.

bigO accumulates its results in a file named bigO_data.json in the local directory; you can then generate a graph of time and space complexity for each tracked function by running python3 -m bigO.graph.

Demonstration

The file test/facts.py is a small program that demonstrates bigO.

import bigO

def fact(x: int) -> int:
  v = 1
  for i in range(x):
    v *= i
  return v

@bigO.track(lambda xs: len(xs))
def factorialize(xs: list[int]) -> list[int]:
  new_list = [fact(x) for x in xs]
  return new_list

# Exercise the function - more inputs are better!
for i in range(30):
    factorialize([i for i in range(i * 100)])

Now run the program as usual:

python3 test/facts.py

Now you can easily generate a graph of all tracked functions. Just run the following command in the same directory.

python3 -m bigO.graph

This command creates the file bigO.pdf that contains graphs like this:

Technical Details

Curve-fitting

bigO's curve-fitting based approach is directly inspired by "Measuring Empirical Computational Complexity" by Goldsmith et al., FSE 2007, using log-log plots to fit a power-law distribution.

Unlike that work, bigO also measures space complexity by tracking memory allocations during function execution. In addition, bigO uses the AIC to select the best model.