New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

O(n*sin(n) + 1, (n, oo)) returns O(n*sin(n), (n, oo)) #9917

Open
gxyd opened this Issue Sep 14, 2015 · 6 comments

Comments

Projects
None yet
4 participants
@gxyd
Copy link
Member

gxyd commented Sep 14, 2015

>>> O(n*sin(n) + 1, (n, oo))
O(n*sin(n), (n, oo))

rather the expression should be returned un-evaluated as O(n*sin(n) + 1, (n, oo))

@jksuom

This comment has been minimized.

Copy link
Member

jksuom commented Sep 14, 2015

It is not clearly stated in the docstring but it seems that O is currently implemented as the "exact order" of an expression. Such an order should be represented by a function positive in at least some neighbourhood of the limit point. Hence O(n*sin(n)) cannot have an order in this sense.

Using the standard "big Oh" interpretation we could say that n*sin(n) is O(n), which means that there is a constant C such that |n*sin(n)| <= C*n (in a neighbourhood of oo). But with this interpretation it would not be possible to determine the "term of highest order" in a sum as no lower bound |n*sin(n)| >= c*n with c > 0 exists.

Perhaps we should have two order functions, the current O and big Oh (real_bound is intended to help implement this).

@gxyd

This comment has been minimized.

Copy link
Member

gxyd commented Sep 14, 2015

it seems that O is currently implemented as the "exact order" of an expression.

The same as i think this to be. I am pretty sure it seems to be working that way for most of the functions.

Perhaps we should have two order functions, the current O and big Oh (real_bound is intended to help implement this).

The value of big Oh is not going to be unique, so do you think that always representing the final result in terms of n**k where k = ..., -2, -1, 0, 1, 2, 3, .... or may be k belongs to ℝ could be used?

@jksuom

This comment has been minimized.

Copy link
Member

jksuom commented Sep 15, 2015

Probably the values of ''big Oh" should belong to the same scale as those of O. There should be no reason for avoiding non-integral powers although "standard" serial expansions do not contain them.

@asmeurer

This comment has been minimized.

Copy link
Member

asmeurer commented Sep 15, 2015

@gxyd

This comment has been minimized.

Copy link
Member

gxyd commented Sep 15, 2015

I had say, yes.
My reason is that:

>>> O(sin(n), (n, oo))
O(sin(n), (n, oo))    # i guess bigOh should return 1

which gives a more of a tight bound. Not the bigOh, the bigOh(sin(n), (n, oo)) should rather make sense to return 1. Atleast i think current O is not working in that(bigOh) manner.

skirpichev added a commit to diofant/diofant that referenced this issue Dec 26, 2015

Add heuristics kwarg for Limit.doit, use it in Order.contains
This is a hack to prevent using heuristics (XXX: think about
better interface).  Fixes sympy/sympy#9917).
@avishrivastava11

This comment has been minimized.

Copy link
Contributor

avishrivastava11 commented Nov 19, 2018

@gxyd Please take a look. I've fixed the issue and added tests

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment