
12 x log(x) versus x^2 in bigO
x log(x) is O(x^2). Proof from definition: for all x>0 log(x) < x, hence
x*log(x)< x^2. But to get x log(x) < x^2, we will only start with those
x bigger than 2 (since log(x) can be a very large negative number when x< 1).
x^2 is not O(x log(x) ). Proof from definition using
contradiction. Suppose it were and fix the constants C, k such
that x^2 < C * x log(x) for all x> k.
Let's take a look at some x> k.
We have then that x < C *  log(x)  since we can cancel an
x from both sides and this is supposed to hold for
all values of x>k. We will produce an integer
x > k for which it is false.
First note that for all positive integers n,
2^n  1 = 1 + ... + 2^(n1) [n terms in sum] > 1 + 1 + ... 1 =
n, thus 2^n > n+1.
Fix a integer n> k+2, such that, in addition, n> C, and set
x=2^(2^(2n)). Hence, log(x) = 2^(2n) and certainly
2^(2^n)> C.
Compute x = 2^(2^(2n)) = 2^(2^n) * 2^(2^n)
> C * 2^(2^n) = C * 2^(2*2^(n1)) > C * 2^(2*n) =
C*log(x)
This last inequality because 2^(n1)> n1 + 1. We've shown
that for this x, x > C*log (x) contradicting the fact that
the reverse inequality is supposed to hold for all x> k.

14 x^3 is O(g(x)) for which g:

x^2. No, assume there are C,k such that for x> k, x^3 <
C x^2
Thus for all x> k, we have x^3/x^2 < C x^2/x^2.
This is obviously not true if we just take any x which is also
> C.

x^2+x^3: Yes, just take C=k=1: x^3 <  x^2+x^3 for all x.

x^2+x^4: Yes just as for the previous.

3^x: Yes but less obvious. We were told to take for granted that
x^n is O(2^x) for all n. Thus x^3 is O(2^x). For very good
practice let us use the definitions and this fact to deduce that
x^3 is O(3^x). By def'n, there are C, k such that x^3 < C 2^x
for all x> k. We also can plainly see that 3^x > 2^x for all
x> 1 (I suppose we can, obvious for integers x, easily
deduced from that for rationals and use approximations for
irrationals).
Thus we have that for all x> max(k,1), x^3 < C * 2^x <
C * 3^x, which shows that the definition of x^3 is O(3^x) is
valid.

x^3/2: Of course, just take k=1, and C=2.

16 If f is O(x), is f also O(x^2)
Sure, fix C,k so that x> k, implies f(x) < C * x,
from the definition of f is O(x). Clearly then f(x)< C * 
x^2 for all x> max(k,1), which is the definition of f is
O(x^2).

18 SUM(i^k : i< n+1) is
O(n^(k+1)).
For each i<n+1, we obviously have that i^k <= n^k, hence the
sum is less than n * n^k = n^(k+1).
Although not asked it is important to know that also n^(k+1) is
bigO of that SUM. There are tricks for proving this, but how
about induction on k: for all n, there is a C_k such that
n^(k+1) < C_k * SUM( i^k : i=0.. n) .
We know this to be true for k=0 and k=1. Now set C_k = 4*C_(k 1)
for some k> 1 and prove it for k.
In the proof I will use that SUM( i^k : i=0..n) < 2 * SUM( i^k
: i = ceiling(n/2).. n) which is easily seen to hold for n>1.
Let's use [n/2] to mean ceiling(n/2).
n^(k+1) = n * n^k < n * C_(k1) * SUM( i^(k1) : i=0..n) (by
induction)
< n * C_(k1) * 2 * SUM( i^(k1) : i=[n/2].. n) <
4 * C_(k1) * (n/2) * SUM( i^(k1) : i = [n/2] .. n);
< 4 * C_(k1) * SUM( i^k : i = [n/2] .. n) (the (n/2) goes
into the sum)
< 4 * C_(k1) * SUM( i^k : i=0.. n) = C_k * SUM( i^k : i=0..n)

20 Simple bigO estimates for
(n^3+n^2 logn)(log n +1) + (17log n + 19)(n^3 + 2) is O(n^3
log(n)), the hardest step is that n^2 log^2(n) is
O(n^3 log(n) ).
(2^n + n^2)(n^3 + 3^n) is O(6^n) since each term in the product,
e.g. n^3 3^n and 2^n * 3^n = 6^n, is O(6^n).
(n^n + n2^n + 5^n)(n! + 5^n), I guess the most reasonable answer
is O(n^n * n!). You could use O( (n^n)^2) = O(n^(2n)) but this is
larger. Note that O(n^n) is incorrect though.

41 and 42 ask if n log n and log
n! have the same bigO (which we need for sorting). Clearly n log
n is bigger than log n!, since n log n = log(n^n) > log(n!).
Thus it is the other direction that is important. The log destroys
the essential difference in size between n^n and n!.
log(n!) > log( (n/2)^(n/2) ) = (n/2) * log(n/2) = (1/2) n
log(n/2) > (1/4) n log( (n/2)^2 ). Finally (n/2)^2=n * (n/4)
> n for all n> 4, hence, log(n!)> (1/4) n log(n).
Well this means that for n> 4, n log(n) < 4 log(n!) which
satisfies the definition of n log(n) is O(log(n!)).