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
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) =
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:
x^2. No, assume there are C,k such that for x> k, |x^3| <
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
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
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
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
18 SUM(i^k : i< n+1) is
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
< 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!)).