Big-O Check: Empirical Complexity Checker for Python

bigocheck is a powerful, zero-dependency empirical complexity checker designed for Python developers. It allows users to empirically measure the time and space complexity of functions via command line interface (CLI), assertions, and integration with pytest. The tool efficiently runs a target function across various input sizes, records runtimes, and fits the results against well-known complexity classes. This dual approach as a library and command-line tool makes it versatile for development and testing workflows.

🌟 Key Features

• Time Complexity Analysis: Fit functions to nine key classes such as O(1), O(log n), O(n log n), and more.
• Space Complexity Classification: Comprehensive detection of memory usage categorized by complexity classes.
• Polynomial Fitting: Detect complex polynomial relationships, including O(n^k) where k is not necessarily an integer.
• Git Commit Tracking: Monitor complexity changes across different commits with support for binary search to identify regressions.
• Threshold Alerts: Automatic alerts when complexity exceeds defined thresholds, catering to continuous integration and deployment workflows.
• Statistical Significance Calculation: Gives p-values to validate complexity classifications, ensuring reliable measurements.
• Interactive CLI and REPL: Facilitates quick analysis and testing via a command-line interface, complete with historical benchmarking and live feedback.
• Rich HTML Reports & Markdown Export: Generate visually engaging reports or markdown files for documentation and sharing results effortlessly.
• Jupyter Integration: Displays analysis directly in Jupyter Notebooks, leveraging rich HTML for enhanced visualization.
• Assertions for CI/CD: Use @assert_complexity and related decorators to ensure code validity against expected complexity, ideal for CI/CD testing environments.

⚙️ Installation Instructions

pip install bigocheck

🚀 Quick Start Example

To benchmark a function, simply run:

bigocheck run --target mymodule:myfunc --sizes 100 500 1000 --trials 3

For library usage:

from bigocheck import benchmark_function

def my_func(n):
    return sum(range(n))

analysis = benchmark_function(my_func, sizes=[100, 500, 1000])
print(f"Best fit: {analysis.best_label}")  # 'O(n)'

📊 Generate Complex Reports

For visually appealing reports, one can generate HTML reports:

generate_html_report(analysis, title="Function Analysis")

🛠 Additional Tools

• Data Generators: Automatically create datasets for testing under various conditions such as sorted and random inputs.
• Confidence Scoring: Know the reliability of benchmark results with a detailed confidence level and reasoning.

🌐 API Reference

bigocheck also includes several core functions and classes, designed to streamline your benchmarking process. Key functions include benchmark_function, fit_complexities, and compare_functions. These additions simplify integration and allow customization for advanced tasks.

Conclusion

With its comprehensive features and focus on performance measurement without external dependencies, bigocheck is an essential tool for Python developers aiming to optimize code performance and maintain high standards in software development.