patternMinor
Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$
Viewed 0 times
timespossiblesimplifyinto
Problem
I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other.
Personally, I think that the simplification is possible. $O(A \times B \times C)$ is a polynomial growth, and (I think) it can be rewritten as $O(A^3)$, $O(B^3)$, or $O(C^3)$. On the other hand, $A^B$ is a exponential growth. As a result, it is possible to omit the left part from the Big O notation.
In other to test my hypothesis, I develop a simple simulation to compare $A \times B \times C$ with $O(A^B)$, the value of $A$, $B$ and $C$ range from 1 to 1000. According to my simulation, there are only $3\%$ chance that $A \times B \times C \geq A^B$. It is enough to omit $A \times B \times C$ from $O(A \times B \times C + A^B)$?
Personally, I think that the simplification is possible. $O(A \times B \times C)$ is a polynomial growth, and (I think) it can be rewritten as $O(A^3)$, $O(B^3)$, or $O(C^3)$. On the other hand, $A^B$ is a exponential growth. As a result, it is possible to omit the left part from the Big O notation.
In other to test my hypothesis, I develop a simple simulation to compare $A \times B \times C$ with $O(A^B)$, the value of $A$, $B$ and $C$ range from 1 to 1000. According to my simulation, there are only $3\%$ chance that $A \times B \times C \geq A^B$. It is enough to omit $A \times B \times C$ from $O(A \times B \times C + A^B)$?
Solution
No, it is not possible. The function $ABC$ is $O(ABC + A^B)$ but not $A^B$, since for no $M$ is it the case that $ABC \leq MA^B$ for large enough $A,B,C$; for any "large enough" $A,B$, this would imply that $C = O(1)$ is bounded, but $C$ need not be bounded.
Context
StackExchange Computer Science Q#62552, answer score: 4
Revisions (0)
No revisions yet.