Building a Python Module for Complexity Calculation

[shahiakhilesh1304]

Hello Everyone,

I hope you're doing well! I’m currently working on a Python module that can be used to calculate the complexity of algorithms. The goal is to provide a tool that helps developers, students, and data scientists easily assess the time and space complexity of their code.

Features I'm Considering:
Time Complexity:

Analysis of code execution time in terms of Big O notation (e.g., O(n), O(log n), O(n^2), etc.)
Provide estimates for worst-case, best-case, and average-case time complexities.
Space Complexity:

Evaluate the space consumed by the algorithm with respect to the input size.
Output the result in Big O notation for space complexity.
Support for Common Data Structures:

Arrays, Linked Lists, Trees, Graphs, Hashmaps, Stacks, Queues, etc.
Use of Decorators to Automate Analysis:

A decorator that wraps any function and reports its time complexity based on the input size.
Challenges & Questions:
What would be the best approach to dynamically analyze algorithm complexity for more complex functions or when working with nested loops/recursion?
How can we reliably determine the space complexity for algorithms that manipulate large data structures?
Any recommendations for improving the accuracy of time complexity estimation?
I would love to hear any thoughts, advice, or contributions you might have regarding this project. If you’re interested in contributing, feel free to comment, and I’ll share more details about the module as it progresses.

Looking forward to your suggestions and insights!

[queenofcorgis]

Thanks for posting in the GitHub Community, @shahiakhilesh1304 !

We’ve moved your post to our Programming Help 🧑‍💻 category, which is more appropriate for this type of discussion.

Please review our guidelines about the Programming Help category for more information.

[shahiakhilesh1304]

Thank you @queenofcorgis for showing the right way.
I've implemented an idea in this repository to analyze the complexity of functions. It's a concept I've been working on to simplify and better understand the performance aspects of code.
I’d greatly appreciate it if you could take some time to review the repository and share your feedback or suggestions for improvements. Your insights and ideas are invaluable and will help make this project even better!

[shahiakhilesh1304]

@queenofcorgis : Can you please Elevate this discussion. I needed a solution and I am not finding this thread much helpful.

[SepehrAkbari]

Thats a very interesting idea.

Time complexity:

My initial thought was to run a function multiple times with increasing input sizes and using regression, fit a curve to approximate complexity using its execution time.

However, I think I got a better idea now with ML. We can start by collecting execution times for different input sizes and extract features like mean, variance and time difference. Then with using a set of known algorithm complexities as our training data, we can train a classifier model and predict. I actually tried this with RandomForestClassifier() and results were pretty good.

Let me know if you want the code. I can share.

Space complexity:

This one's pretty easy, just use sys.getsizeof() before and after usage and add them up.

Please mark this answer helpful!

[shahiakhilesh1304]

also i have been looking to the way to take the memory usage and i came across a article where it was mentioned as it doesn’t count all the bytes, and it counts the wrong bytes.
ARTICLE

Can you help me to understand this even deeper

[SepehrAkbari]

Hey,

So here is the code I wrote very roughly to test it with Random forest Classifier. Its working pretty good.

Let me know if you see room for improvement or want me to explain something. Also, would appreciate it if you mark my response as 'answer'.

import time
import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
import warnings

warnings.filterwarnings("ignore")

def constant(n): return 1
def logarithmic(n): return np.log(n)
def linear(n): return n
def n_log_n(n): return n * np.log(n)
def quadratic(n): return n ** 2
def cubic(n): return n ** 3
def exponential(n): return 2 ** n

complexity_classes = {
    "O(1)": constant,
    "O(log n)": logarithmic,
    "O(n)": linear,
    "O(n log n)": n_log_n,
    "O(n^2)": quadratic,
    "O(n^3)": cubic,
    "O(2^n)": exponential
}

n_values = [10, 50, 100, 500, 1000]
data = []

for label, func in complexity_classes.items():
    for _ in range(100): 
        n = np.random.choice(n_values)
        time_taken = func(n) + np.random.normal(0, 0.1) 
        data.append([n, time_taken, label])

df = pd.DataFrame(data, columns=["n", "time", "complexity"])

df["complexity"] = df["complexity"].astype("category").cat.codes

X = df[["n", "time"]]
y = df["complexity"]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

model = Pipeline([
    ("scaler", StandardScaler()),
    ("classifier", RandomForestClassifier(n_estimators=100, random_state=42))
])

model.fit(X_train, y_train)

print(f"Model Accuracy: {model.score(X_test, y_test) * 100:.2f}%")

def estimate_complexity(f, n_values=[10, 100, 500, 1000, 5000]):
    times = []
    
    for n in n_values:
        data = list(range(n)) 
        start = time.time()
        f(data)
        end = time.time()
        times.append(end - start)

    prediction = model.predict([[n_values[-1], times[-1]]])[0]
    complexity_label = df["complexity"].astype("category").cat.categories[prediction]
    
    print(f"Predicted Time Complexity: {complexity_label}")

@estimate_complexity
def example_function(arr):
    return [x**2 for x in arr]

[SepehrAkbari]

Oh also, thanks for sharing the Article. I understand that these sorts of functions come with short comings, and calculating space complexity can go from simple to extremely complex really fast. What I suggested was a way to perhaps calculate complexity of simple and semi-simple function. Speaking of which, I elevated the idea I gave you a little:

def space_complexity(f):
    def wrapper(*args, **kwargs):
        before = sys.getsizeof(args) + sys.getsizeof(kwargs)
        result = f(*args, **kwargs)
        after = sys.getsizeof(result)
        total_space = after + before
        print(f"Estimated Space Usage: {total_space} bytes")
        return result
    
    return wrapper

But if I were you, I would rely on a language like C to calculate space complexity, not Python. Because of the issues that the article also mentions.

[shahiakhilesh1304]

Hey,

So here is the code I wrote very roughly to test it with Random forest Classifier. Its working pretty good.

Let me know if you see room for improvement or want me to explain something. Also, would appreciate it if you mark my response as 'answer'.

import time
import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
import warnings

warnings.filterwarnings("ignore")

def constant(n): return 1
def logarithmic(n): return np.log(n)
def linear(n): return n
def n_log_n(n): return n * np.log(n)
def quadratic(n): return n ** 2
def cubic(n): return n ** 3
def exponential(n): return 2 ** n

complexity_classes = {
    "O(1)": constant,
    "O(log n)": logarithmic,
    "O(n)": linear,
    "O(n log n)": n_log_n,
    "O(n^2)": quadratic,
    "O(n^3)": cubic,
    "O(2^n)": exponential
}

n_values = [10, 50, 100, 500, 1000]
data = []

for label, func in complexity_classes.items():
    for _ in range(100): 
        n = np.random.choice(n_values)
        time_taken = func(n) + np.random.normal(0, 0.1) 
        data.append([n, time_taken, label])

df = pd.DataFrame(data, columns=["n", "time", "complexity"])

df["complexity"] = df["complexity"].astype("category").cat.codes

X = df[["n", "time"]]
y = df["complexity"]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

model = Pipeline([
    ("scaler", StandardScaler()),
    ("classifier", RandomForestClassifier(n_estimators=100, random_state=42))
])

model.fit(X_train, y_train)

print(f"Model Accuracy: {model.score(X_test, y_test) * 100:.2f}%")

def estimate_complexity(f, n_values=[10, 100, 500, 1000, 5000]):
    times = []
    
    for n in n_values:
        data = list(range(n)) 
        start = time.time()
        f(data)
        end = time.time()
        times.append(end - start)

    prediction = model.predict([[n_values[-1], times[-1]]])[0]
    complexity_label = df["complexity"].astype("category").cat.categories[prediction]
    
    print(f"Predicted Time Complexity: {complexity_label}")

@estimate_complexity
def example_function(arr):
    return [x**2 for x in arr]

This was my initial approach to analyzing complexity, but the issue with this method is that it only works for a specific type of input defined in estimate_complexity().

I have another approach in my codebase that addresses this limitation. You can check it out here: ANALYZER. Can you suggest more improvement to this.

[shahiakhilesh1304]

Oh also, thanks for sharing the Article. I understand that these sorts of functions come with short comings, and calculating space complexity can go from simple to extremely complex really fast. What I suggested was a way to perhaps calculate complexity of simple and semi-simple function. Speaking of which, I elevated the idea I gave you a little:

def space_complexity(f):
    def wrapper(*args, **kwargs):
        before = sys.getsizeof(args) + sys.getsizeof(kwargs)
        result = f(*args, **kwargs)
        after = sys.getsizeof(result)
        total_space = after + before
        print(f"Estimated Space Usage: {total_space} bytes")
        return result
    
    return wrapper

But if I were you, I would rely on a language like C to calculate space complexity, not Python. Because of the issues that the article also mentions.

I can't rely on C language since my goal is to create an importable Python module. This way, I can simply import it into a Python script and analyze the complexity of the code seamlessly.

[ghost]

Your project sounds like a great tool for developers! For dynamic time complexity analysis, consider using AST (Abstract Syntax Tree) to analyze loop structures and recursion patterns. You can also use profiling tools like cProfile or timeit for empirical measurements. For space complexity, track memory usage with sys.getsizeof() and tracemalloc. To improve accuracy, combine static code analysis with runtime profiling to refine Big O estimations based on varying input sizes. Would love to see how this evolves! 🚀

[shahiakhilesh1304]

@lz000218,
Thanks for your insights! I hadn’t explored AST in depth before, but it sounds like a powerful approach for analyzing loop structures and recursion patterns; I’ll definitely look into it.

For profiling, timeit doesn’t seem ideal for my use case, as I want to integrate this directly into my project. The goal is to create a module that can be imported into any Python file within the repository and automatically analyze its time and space complexity.

cProfile looks bit promising, and I’ll be researching how to build a module around it. Your suggestion about combining static code analysis with runtime profiling is great; this could significantly improve accuracy. I’d love to hear any further thoughts you might have as I develop this!

(For further development i would need your input.)

[Rishi-Sudhakar]

Check this, code . Try it out!

      from complexity_analyzer import ComplexityAnalyzer
      @ComplexityAnalyzer().analyze
      def your_function(args):
          # Your code here
          pass

[shahiakhilesh1304]

This looks promising, let me check through the code and then get back to you on this..