How to Perform Operations on Big O Terms?

[Avichal]

Is there a standard algorithm or procedure that defines addition, multiplication of big O terms.

I want definitions for problems like:-
1) (x-1) * O(x)
2) O((x-a)²) where a is some positive number
etc.

Since I want to implement this on a computer I would prefer some algorithm or paper that defines and tells you how to deal with operations on big O terms.
Thank you!

 

[voko]

The very first hit for "big O notation" was http://en.wikipedia.org/wiki/Big_O_notation =. Now I believe you would not have posted questions, answers to which are so easily found, so I assume there is a problem with that page. What is it?

 

[Avichal]

Yes, I had a look at the Wikipedia page. It's great but I wanted something more algorithmic.
I am looking for something like a research paper which would algorithmic-ally explain how to compute order of an expression.
For e.g.:- O(x) + O(y) .. multivariate order arithmetic is tough to handle
O(x-a) .. order around some arbitrary point

Basically I want it from the perspective of implementing a computer algebra system (CAS)

 

[voko]

I am not aware of such papers and I am not convinced this is something one should be bothered with. The big O notation is used almost exclusively with very particular arguments, such as powers of a variable or logarithms. The notation itself is never the most difficult, or even just difficult, thing in any research. Finding an estimate is the difficult part, wrapping it in the big O notation is trivial.

I suggest that you tackle something more useful.

 

[LudusRex]

I understand the importance of efficiency and scalability in algorithms, which is where Big O notation comes into play. Big O notation is a mathematical notation used to describe the time complexity or space complexity of an algorithm. It is commonly used in computer science to analyze and compare the efficiency of different algorithms.

To address your questions, there is not a single standard algorithm or procedure that defines addition and multiplication of Big O terms. However, there are some general rules and guidelines that can be followed.

1) For the expression (x-1) * O(x), we can simplify it by distributing the O(x) term, resulting in x * O(x) - 1 * O(x). Since the O(x) term represents a function that grows at most as fast as x, we can simplify further to just O(x^2) - O(x). This can then be simplified to just O(x^2) using the rule that when adding or subtracting two Big O terms, we take the highest order term.

2) For the expression O((x-a)^2), we can use the same simplification process as above to get O(x^2 - 2ax + a^2). However, since a is a fixed positive number, we can ignore the constant term a^2 and simplify it to just O(x^2 - 2ax).

It is important to note that these are just general guidelines and the simplification process may vary depending on the specific expressions and terms involved. Additionally, there are also rules for other operations such as division, logarithms, and exponentiation of Big O terms, but they can be more complex and may require further analysis.

In terms of implementation on a computer, there are various resources and papers available that provide more in-depth explanations and examples of operations on Big O terms. It is recommended to consult these resources and potentially seek guidance from a computer science expert to ensure accurate and efficient implementation.