big_O is buggy

[anurudhp]

big_O only takes into account all variables in the input expression (setting their limit to inf), but not once multiplied later.

import sympy
from qualtran.resource_counting import big_O

n = sympy.Symbol("n", positive=True)

print(big_O(1) * n) # O(n)
print(big_O(1) * (1 / n)) # O(1/n)
print(big_O(1) * (n + 1)) # O(1)
print(big_O(1) * (1 / n + 1)) # O(1/n)

Also, sympy does not support multivariate orders. And as we usually have variables tending to both limits, e.g. n, m etc to inf, and eps, delta etc to 0, using big_O might lead to incorrect expressions.

---

One option would be to instead return C * E instead of big_O(E) in call graphs etc. And while viewing expressions, the user can take big_O of the whole thing. Could possibly use SympySymbolAllocator to generate these constants.

[mpharrigan]

You mean just include an arbitrary constant $C$ in the returned expression for a bloq?