• 12 x log(x) versus x^2 in big-O
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^(n-1) [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^(n-1)) > C * 2^(2*n) = C*log(x)
This last inequality because 2^(n-1)> n-1 + 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:

1. 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.

2. x^2+x^3: Yes, just take C=k=1: |x^3| < | x^2+x^3| for all x.
3. x^2+x^4: Yes just as for the previous.
4. 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.

5. 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 big-O 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_(k-1) * SUM( i^(k-1) : i=0..n) (by induction)
< n * C_(k-1) * 2 * SUM( i^(k-1) : i=[n/2].. n) < 4 * C_(k-1) * (n/2) * SUM( i^(k-1) : i = [n/2] .. n); < 4 * C_(k-1) * SUM( i^k : i = [n/2] .. n) (the (n/2) goes into the sum)
< 4 * C_(k-1) * SUM( i^k : i=0.. n) = C_k * SUM( i^k : i=0..n)

• 20 Simple big-O 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 big-O (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!)).