I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; What I would like to ask, if there is a certain way to find out O-Notation? Actually I know that the purpose of O-Notation, it helps us to estimate the effciency of algorithm. But in a specific questions like O(2^n) * O(n^10) I assumed that O(2^n * n^10) as in the worst case but learned that I was false, it should be 2^n and I don't know why? Shouldn't we think that which term would go faster to eternity, and in this case I thought that when I multiply both then it can go faster than 2^n, can't it? Could anyone explain please ? Just short and with beginner sight:)

  • $\begingroup$ Yes, your are right that $O(2^n) * O(n^{10}) = O(2^n * n^{10})$. $\endgroup$
    – John L.
    Dec 16 '20 at 21:18
  • $\begingroup$ Our Professor said that O(2^n) must be. Because O(n^10) can be ignored due to very slow growth rate compare to 2^n. $\endgroup$ Dec 16 '20 at 21:32
  • 1
    $\begingroup$ This is correct when talking about addition. When talking about multiplication, this kind of thing cannot be ignored $\endgroup$
    – nir shahar
    Dec 16 '20 at 21:42
  • $\begingroup$ I am really confused right now:) I knew that I was right but then checked my classmate and he said also this is 2^n.But anyway, thanks for you all for helping $\endgroup$ Dec 16 '20 at 23:03
  • $\begingroup$ If I have to guess, the question was about some algorithm, which consists of two parts. Since the parts are not nested, their running times should be added, not multiplied. $\endgroup$
    – user114966
    Dec 17 '20 at 12:33

We can show that $O(2^n\cdot n^{10}) \not\subset O(2^n)$:

As $2^n\cdot n^{10} \in O(2^n\cdot n^{10})$, then, if also holds $2^n\cdot n^{10} \in O(2^n)$ then we will have $2^n\cdot n^{10} \leqslant C 2^n$, which gives false $n^{10} \leqslant C$.


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.