Dominance and Big Oh problem

116 Views Asked by At

What is the dominant term in the following expression?

100n + 0.01*(n^2)

It is confusing because the power function should be growing faster than the linear function regardless the constants. But trying to sketch both functions on the same graph shows how the linear is dominating the quadratic term, which is confusing

2

There are 2 best solutions below

0
On

IT is certainly $n^2$. What you need to do is find $n_0$, for which $100 n < 0.01 n^2$. Then you immediately get that your expression is less than $0.02 n^2 = O(n^2)$

0
On

$n^2$ is the dominant term. You don't see that effect because you're looking at relatively small values. The point of asymptotic analysis is to compare growth of a function, which can often only be seen at extremely large values of $n$. For instance, if you graph the two from $n=0$ to $n=1,000,000$, you'll see that $100n$ is practically gone.