How can big O's have values of the form A+B?

  • MHB
  • Thread starter find_the_fun
  • Start date
  • Tags
    Form
In summary: O} (g_{1})$ $\displaystyle g_{1} \in \mathcal{O} (g_{2})$ $\displaystyle f_{2} \in \mathcal{O} (g_{1}+g_{2})$
  • #1
find_the_fun
148
0
For example according to wikipedia and this question bucket sort has the expected time complexity O(n+k). How does it make sense to use big O notation with arithmetic in it? Is it because it is not known which of n or k will determine the upper bound but once it is known (i.e. the algorithm is implemented) then it would be known if it actually is O(n) or O(k)?
 
Technology news on Phys.org
  • #2
find_the_fun said:
For example according to wikipedia and this question bucket sort has the expected time complexity O(n+k). How does it make sense to use big O notation with arithmetic in it? Is it because it is not known which of n or k will determine the upper bound but once it is known (i.e. the algorithm is implemented) then it would be known if it actually is O(n) or O(k)?

To say that \(f(n,k)\in O(n+k)\) means that there exists a \(C>0\) such that for \(n+k\) large enough:

\[|f(n,k)| < C |n+k|\]

That is they jointly define the bound on the growth of \(|f(x,k)|\)

CB
 
  • #3
find_the_fun said:
For example according to wikipedia and this question bucket sort has the expected time complexity O(n+k). How does it make sense to use big O notation with arithmetic in it? Is it because it is not known which of n or k will determine the upper bound but once it is known (i.e. the algorithm is implemented) then it would be known if it actually is O(n) or O(k)?

One of the basic property of the 'big-O notation' is that, if f and g are positive functions, then ... $\displaystyle f_{1} \in \mathcal{O} (g_{1})\ \text{&}\ f_{2} \in \mathcal{O} (g_{2}) \implies f_{1}+f_{2} \in \mathcal{O} (g_{1}+g_{2}) $

Kind regards

$\chi$ $\sigma$
 

FAQ: How can big O's have values of the form A+B?

Can you explain what big O notation is and how it relates to the values of A and B?

Big O notation is a mathematical notation used to describe the asymptotic behavior of a function. It is commonly used in computer science to analyze the time or space complexity of algorithms. In this context, A and B represent constant factors that can affect the overall running time or space usage of an algorithm. However, as the input size grows, these constants become insignificant and are therefore not included in the big O value.

How can two different algorithms have the same big O value with different values for A and B?

Two algorithms can have the same big O value if they have the same asymptotic behavior, meaning that their time or space complexity grows at the same rate as the input size increases. The values of A and B may differ due to variations in the way the algorithms are implemented or the data they are operating on. However, as the input size grows, these differences become insignificant and do not affect the overall complexity of the algorithms.

Why are the values of A and B excluded from the big O notation?

The purpose of big O notation is to provide a general understanding of the complexity of an algorithm without getting into the details of its implementation. Including the values of A and B would make the notation more specific to a particular algorithm and would not provide a clear picture of its overall complexity. Additionally, as the input size increases, the impact of these constants becomes negligible, making them irrelevant in the big O analysis.

Can big O values of the form A+B be compared to those of the form C+D?

Big O notation is used for comparison between algorithms in terms of their complexity, not for comparing the values of A and B themselves. The values of A and B can vary depending on the specific implementation or data, but as long as the big O values are the same, the algorithms can be considered to have the same complexity. However, if two algorithms have different big O values, it is not possible to directly compare the values of A and B as they represent different orders of growth.

Are there any limitations to using big O notation to analyze algorithmic complexity?

Big O notation is a useful tool for analyzing the complexity of algorithms, but it does have some limitations. It only considers the worst-case scenario and does not take into account best or average case performance. Additionally, it does not consider factors such as the hardware or programming language being used, which can also affect the performance of an algorithm. Therefore, while big O notation is a valuable tool, it should not be the only factor considered when evaluating the efficiency of an algorithm.

Back
Top