Algorithm Analysis - Proof of Anonymous Function

Question

Based on the definition of Big-Theta (or Big-O), how do I go about solving/proving an equation of this format: An^2+ Θ(n) = Θ(n^B) where A and B are some constants (i.e. there is an O(n) on both sides).

I know how to solve/prove Big-O and Big-Omega, but I'm completely lost on how to find c1, c2 and n when an anonymous function is involved.

An example of both Big-O and Big-Theta would be appreciated (lets use A=2, and B=2 for both examples).

Answer 1

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.