Note that An^2 + Theta(n)
is in Theta(n^B)
if and only if B == 2
.
Let's assume it from now on.
From definition of Big Theta, we know that Theta(n) is also O(n), and thus there is c1 and N1 such that for all n > N1: An^2 + Theta(n) <= An^2 + c1*n
.
We also know that there are c2,N2 such that for all n>N2 An^2 + c1*n <= c2*n^2
. We just got that by definition of big O - An^2 + Theta(n)
is in O(n^2)
(with the constant c2
and N=max(N1,N2)
), Similarly show for Omega(n^2), and you have shown An^2 + Theta(n)
is in Theta(n^2)
by definition.