3
$\begingroup$

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)$?

$\endgroup$
  • 3
    $\begingroup$ Computing a finite set of values does not tell you anything about Big-Ohs. Despite the way many people flick them around, these are mathematical objects and not shorthands for rough intuitions. Check their definition! $\endgroup$ – Raphael Aug 13 '16 at 16:13
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

No you can't. As you said the three variables are independent of each other. If I want to study the complexity keeping $A$ and $B$ constant then the first term has significance as I can't bound $C$ if $A$ and $B$ are constant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.