Suppose there is a function f(x)= 19n^2/5n +1-n
I want to calculate upper and lower bound. But I had this confusion that whether I have to calculate in terms of n^2? Because dominating term is n^2
or If I solve the above equation as f(x)= 19n/5 +1-n (canceling n in 1st term) then what? Then I have to calculate c1 and c2 in terms of n? because that will be the dominating term .
So, Kindly tell me that in which term do I have to calculate c1 and c2 i.e n or n^2?? Can I cancel n in 19n^2/5n or not? What will be its asymptotic form? f(n)∈Θ(n^2) or f(n)∈Θ(n) ?
Well if you have
f(n) = 19n^2 / (5n) - n + 1
you can, for the purpose of finding asymptotic bounds, indeed cancel out the n's to obtain
f(n) = (19/5)n - n + 1 = (14/5)n + 1
The easy way to do this is observing that (14/5)n is a dominating term here so +1 can be ignored, and 14/5 is a (positive) constant which can therefore also be ignored.
Therefore, we have that f(n) ∈ Θ(n).
In terms of lower and upper bound coefficients c1 and c2, this can be motivated by the fact that you can find two such coefficients (greater than zero!) such that c1 * n is asymptotically smaller than f(n), whereas c2 * n is asymptotically larger than f(n). For instance, consider c1 = 1 and c2 = 3.