Determine if each of the following are **O(x^2)**
- 17x+11
- x^2+1000
- x * log(x)
- x^4 /2
- 2^x
- floor(x) * ceiling(x)

- yes, 17x + 11 is O(x^2). We can easily use our theorem that
says that if f and g are both O(h), then so is f+g. For x > 17,
x^2 is bigger than 17x, hence 17x is O(x^2). 11 is
**clearly**
O(x^2). Therefore 17x + 11 is O(x^2).
- Similar to the previous part, both x^2 and 1000 are O(x^2),
hence so is the sum.
- x*log(x) is O(x^2). This can be seen as follows: x is O(x)
and log(x) is also O(x). Therefore we take products: x*log(x) is
O(x*x) which is O(x^2). Note we cannot say that x*log(x) is O(x)
like in parts 1 and 2, because that only worked for sums not
products. That is, if f is O(h) and g is O(h), we can only say
that f*g is O(h*h), we cannot say that f*g is O(h).
- No x^4 /2 is not O(x^2). Proof, can there be a C such that
for large enough x,
** x^4 /2 < C*x^2**? Can assume that x
is bigger than 0, so we can divide both sides by x^2. We would
then need that ** x^2 /2 < C** for all sufficiently big x.
Of course this is not true if x is bigger than 2*C.
- Again, no 2^x is not O(x^2). This is one of those "take it
for granted" pairs. Or if you like we could take logs. E.g. if we
had C such that
** 2^x < C* x^2** for all big enough x. But
if we take logs we get ** log(2^x) < log( C*x^2 ) **. Then
simplify ** log(2^x) = x * log(2) = x ** (since we use log
base 2). Also ** log( C * x^2) = log(C) + 2*log(x)**. We are
left with

** log(2^x) = x < log(C) + 2 * log(x)** or

** x < log(C) + 2*log(x)< 3*log(x)** as long as **x**
is bigger than C (to absorb the log(C)). But since we know that
**x** is not O(log(x)), we know this can't be true.
- floor(x) * ceiling(x) is approximately equal to x^2 so it
must surely be O(x^2). Since floor(x) is O(x) and we have our
theorem about products of functions, it suffices to show that
ceiling(x) is O(x). Since ceiling(x) < x+1, this is rather
clear.