How to Perform Operations on Big O Terms?

In summary, the conversation discusses the need for an algorithm or research paper that explains how to compute addition and multiplication of big O terms, particularly for implementing a computer algebra system. The Wikipedia page on big O notation is mentioned, but the individual is looking for a more algorithmic approach. However, it is noted that the big O notation is not usually the most difficult aspect of research and suggests focusing on something more useful.
  • #1
Avichal
295
0
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)2) 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!
 
Technology news on Phys.org
  • #2
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?
 
  • #3
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)
 
  • #4
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.
 
  • #5


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.
 

FAQ: How to Perform Operations on Big O Terms?

1. What is the purpose of Big O notation in algorithms?

Big O notation is a way of measuring the efficiency of an algorithm by analyzing how its runtime or space requirements change as the input size increases. It allows us to compare different algorithms and determine which is more efficient for solving a particular problem.

2. How is Big O notation calculated?

Big O notation is calculated by looking at the algorithm's worst-case scenario. This means considering the input size n and determining how many steps the algorithm will need to take to complete the task. The number of steps is then expressed in terms of n, and any constant factors or lower order terms are dropped. The resulting expression is the Big O notation for that algorithm.

3. What is the difference between time complexity and space complexity in Big O notation?

Time complexity in Big O notation refers to how long it takes for an algorithm to run as the input size increases. Space complexity, on the other hand, refers to how much memory or storage an algorithm needs to complete the task as the input size increases. Both time and space complexity are important factors to consider when analyzing the efficiency of an algorithm.

4. Can Big O notation be used for all types of algorithms?

Yes, Big O notation can be used for all types of algorithms, including sorting, searching, and graph algorithms. It can also be applied to both iterative and recursive algorithms.

5. How can Big O notation be useful for practical applications?

Big O notation allows us to make informed decisions when choosing between different algorithms for solving a problem. It can also help us optimize our code by identifying areas where we can improve efficiency. Additionally, Big O notation is commonly used in software engineering interviews to assess a candidate's problem-solving skills and understanding of algorithmic efficiency.

Back
Top