# How to identify Dominant terms in big-O notation and understand Time Complexity of an algorithm?

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

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.

• 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))' ? Aug 12 at 10:38
• @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 Aug 12 at 10:45

$$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{3^n}=(\sqrt3)^n.$$

The first function is linear and the second exponential.

• 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? Aug 12 at 10:43
• @PolamreddyVivekReddy: that does not matter.
– user16034
Aug 13 at 14:18