deduce_asymptotics is a Python package for deducing the time complexity of functions in big-O notations. It allows you to collect runtime data for a function, fit different time complexity models to the data, and visualize the results with both regular and logarithmic scales.
To install the package directly from the GitHub repository, use the following commands:
git clone https://github.com/mkhlyzov/deduce_asymptotics.git
cd deduce_asymptotics
pip install .Or the editable installation:
pip install -e .After installing the package, you can use it in your Python code as follows:
from deduce_asymptotics import Deduce
def build_input(n):
# Implement your input data generation logic here
pass
def your_function(input_data):
# Implement your function to be tested here
pass
# Call deduce_asymptotics with your input generation and function
ded = Deduce(your_function, build_input)
ded.deduce(time_budget=10, num_samples=10)
# time budget (seconds): Total amount of time the program is allowed to run. More of a soft upper boundary.
# num_samples (int): Number of times function has to be evaluated at each point. Accounts for stochasticity.
ded.report()
ded.plot()To customize the rate at which input length gets changed:
ded.deduce(
time_budget=10, num_samples=5,
step=lambda n: n + 100,
start=100,
verbose=True
)For DETAILED walk-through of how to use the package, check out the examples folder in the GitHub repository.
This project is licensed under the MIT License - see the LICENSE file for details.
If you would like to contribute to this project, please submit a pull request or open an issue on the GitHub repository.