3
$\begingroup$

I understand that Time Complexity is the measure of how an algorithm scales with respect to the input size.
Let us say an algorithm is having a runtime of O($3^n$) + O($n^{20}$)

In order to identify the Non-Dominant term, I followed my intuition for a sample of values:
$3^n$ = {1, 3, 9, 27, ...} for n={0, 1, 2, ...}
$n^{20}$ = {0, 1, 1048576, 3486784401, ...} for n={0, 1, 2, ...}

I see that $n^{20}$ scales up more quickly than $3^n$ for all values of n>=2
Can I say in this regard that the Non-Dominant term is $3^n$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

No, when we talk about dominant terms in big-O notation we talk about asymptotic domination, i.e. how terms scale as $n \to \infty$. To see this you can think about the limit: $$\lim_{n \to \infty}\frac{f(n)}{g(n)} = C \ .$$

If this value is $C \in \mathbb{R}$, then we have that $f(n)=O(g(n))$ and so the sum $O(f(n))+O(g(n))=O(g(n))$.

If instead, $C=+\infty$, then it's the opposite, i.e. $g(n)=O(f(n))$ and so the sum will be $O(f(n))+O(g(n))=O(f(n))$.

In your case, even if for small values of $n$ it seems that $n^{20}$ grows faster than $3^n$, this is not the case.

Indeed, $\lim_{n\to \infty} \frac{3^n}{n^{20}} = + \infty $.

You can see it in this way: $3^n=(3^{\log_3 n})^{n/\log_3 n}=n^{n/\log_3 n}$ which grows obviously bigger than $n^{20}$, in particular it surpasses $n^{20}$ as soon as the exponent $\frac{n}{\log_3 n}$ surpasses $20$.

It it worth to notice that asymptotic behavior isn't everything. In practice, polynomials with large exponents or large multiplicative constants can be bigger than exponentials for values of $n$ from real world applications.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you elaborate or share a reference to understand about 'If this value is C∈R , then we have that f(n)=O(g(n)) and so the sum O(f(n))+O(g(n))=O(g(n))' ? $\endgroup$
    – PolamreddyVivekReddy
    Aug 12 at 10:38
  • 1
    $\begingroup$ @PolamreddyVivekReddy the fact that if the limit is a real value than $f(n)=O(g(n))$ comes directly from the definition of big-O notation (en.wikipedia.org/wiki/Big_O_notation). The fact that the sum $O(f(n))+O(g(n))$ is also a consequence of the definition (assume $g$ is the dominant term, than the quotient between $(f+g)/g$ is limited). It is better to write $O(f(n)+g(n))$, which is the correct notation. Regarding the last question, re-writing a function does not change its behavior, it is just another way of writing the same thing where the functions we use are well-defined $\endgroup$
    – SilvioM
    Aug 12 at 10:45
2
$\begingroup$

Numerical examples can be misleading.

$$100^{20}=10000000000000000000000000000000000000000, \\3^{100}=515377520732011331036461129765621272702107522001.$$

When you consider the ratios $\dfrac{T(n+1)}{T(n)}$, you get

$$\frac{(n+1)^{20}}{n^{20}}=\left(1+\frac1n\right)^{20}\sim1+\frac{20}n\to1$$ and $$\frac{3^{n+1}}{3^n}=3.$$

So in fact the second function grows much faster !

Another argument is by taking the $20^{\text{th}}$ roots of both functions, to get

$$n$$

vs.

$$\sqrt[20]{3^n}=(\sqrt[20]3)^n.$$

The first function is linear and the second exponential.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If we re-write original functions as mentioned in the answer, Aren't we changing their natural behavior because their graphical plots seem different to me? $\endgroup$
    – PolamreddyVivekReddy
    Aug 12 at 10:43
  • 1
    $\begingroup$ @PolamreddyVivekReddy: that does not matter. $\endgroup$
    – user16034
    Aug 13 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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