Big Oh Notation and Big Theta Notation Simplifying

Question 1

(There's a TLDR at the end specifically about your question, I thought I'd give you a little bit about big-O as well)

Maybe something that's more palpable than formalism: this O-notation stuff is supposed to compare functions according to their growth. If you compare polynomials according to their growth, then all you have to look at is the highest exponent (i.e. their "degree"): if they have the same degree, then they grow about as quickly as each other. If one has a higher degree than the other, then the one with the higher degree grows faster than the other.

So from that and some middle school math, we know immediately that 2n+5 = O(n^2) since any quadratic function (with a positive factor for the n^2) at some point outgrows any linear function.

Now back to the formalism; we also want to capture the idea that two functions grow "roughly equally fast". For example, all linear functions of positive growth grow roughly equally fast. For that we want to introduce the scaling factor c: we say f = O(g) if f(n) <= c*g(n). With that scaling, we see immediately that all linear functions grow "roughly equally fast": take f(n) = a*n + b and g(n) = k*n + d, then you can rescale g using the scaling factor a/k and get a/k * g(n) = a*n + d*a/k; so now a/k * g(n) and f(n) grow equally fast and their absolute difference is reduced to a constant value.

For a linear and a quadratic function, we can't do that; no matter how much we rescale the linear function, the quadratic one will always grow faster. You can see that from their derivatives, for example; the derivative of a linear function is a constant, and that of a quadratic function is a linear function, so the growth of the quadratic function always increases while that of the linear function stays the same.

The last part of the big-O definition is the bit about "for all n > n_0 for some n_0"; the reason we do this is because even though if g grows faster than f, initially f may have the higher values. Compare for example g(n) = n^2 and f(n) = n + 2^200. Initially, no matter how much you rescale, f(1) will be bigger than c*g(1). We don't want to bother with stuff like that, so we say "if at some point c*g is above f and stays above it, that's good enough for our purposes". That's where the "(there exists a c such that) there exists an n_0 such that for all n > n_0: f <= c*g" comes in.

Now back to your question: You want to show that there is a c and an n_0 such that for all n > n_0, we have 2n+5 <= c*n^2. Now what you have to make sure here is that c is a NUMBER, not a function, so setting c = 7/n is out of the question. But you can actually pick an arbitrary positive c and see if you can just resolve the inequation; I'll show it for c = 3:

2n+5 <= 3*n^2

0 <= 3*n^2 - 2n - 5

Now the roots of 3*n^2 - 2n - 5 are 10/6 and -1, which means before -1, the inequality holds, between -1 and 10/6 we are below 0, and after 10/6 the inequality holds again. This means we pick the first natural number after 10/6 as our n_0, so we get n_0 = 2.

Regarding x^4.2/(1+x^2), we get 0.5*x^2.2 = x^4.2/(2x^2) < x^4.2/(1+x^2) for x > 1 and x^4.2/(1+x^2) < x^4.2/x^2 = x^2.2 for all positive x.

For x^3 lg x, you're done, there's not really a simpler expression for that. You can of course give upper bounds without using the logarithm, but you don't really have to.

Question 2

2n+5 is O(n^2)

If you choose k = 1, then you need to find n0 such that, for all n > n0, n^2 > 2n + 5. For example n0 = 4. Another ways is to evaluate lim 2n+5/n^2 when n -> inf. Because lim (n->inf) 2n+5/n^2 = 0, we can say that 2n+5 is o(n^2) (small o) which implies big O notation 2n + 5 is O(n^2).

(x^(4.2))/(1+x^2) it is reasonable to say that it is Theta(x^2.2) because you can find constant k1, k2 such that for all x>x0, k1*x^2.2 <= (x^(4.2))/(1+x^2) <= k2 * x^2.2.

x^3*lg(x)

The most reasonable answer is that x^3*lg(x) is O(x^4), because lg(x) is O(x) and big O notation product property.