Determine if each of the following are O(x^2)
  1. 17x+11
  2. x^2+1000
  3. x * log(x)
  4. x^4 /2
  5. 2^x
  6. floor(x) * ceiling(x)
  1. 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).
  2. Similar to the previous part, both x^2 and 1000 are O(x^2), hence so is the sum.
  3. 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).
  4. 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.
  5. 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.
  6. 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.