CPSC 170 Prelab 6
Computational Complexity

The big-Oh relationship can be defined as follows: Definition of Big Oh: Let f and g be functions mapping nonnegative reals into nonnegative reals. Then f is big-Oh of g, written f=O(g), if there exist positive constants n0 and c such that for x >= n0, |c*f(x)| <= |g(x)|.

Example 1

In class we used the following example: 
f(x) = 4x+5
g(x) = x
We found that the rule above holds for c = 1/5 and n0 = 5. Look at a few values:
  x   f(x) = 4x + 5 g(x) = x 1/5*f(x)
1 9 1 9/5 = 1 4/5
3 17 3 17/5 = 5 2/5
5 25 5 5
7 33 7 33/5=6 2/5
9 41 9 41/5 = 8 1/5

Notice that f(x) > g(x) everywhere. However, we see that 1/5 f(x) <= g(x) for x >= 5. (The table above does not prove this, but it's easy to do algebraically.) Thus for our f and g it is true that f(x) = O(g(x)) and for proof we need only offer c = 1/5 and n0 = 5.

Example 2

Now look at the following functions: 
f(x) = 4x2+5
g(x) = x
We are looking for c and n0 such that for all x >= n0, |c*(4x2 + 5)| <= |x|. Clearly we will need c < 1, as before. Let's try 1/100:
  x   f(x) = 4x2 + 5 g(x) = x 1/100*f(x)
1 9 1 9/100
3 41 3 41/100
5 105 5 105/100
7 201 7 201/100
Although 1/100 f(x) is less than g(x) for x=1..7, will it stay that way? Try greater values to see. Where does it become false?



It turns out that no matter what value we choose for c, we can choose x such that c*f(x) > g(x) (this can be shown algebraically as well).

Problems

Each item below gives functions f(x) and g(x) such that f(x)=O(g(x)). For each f and g, provide this relationship by finding c and n0 to satisfy the definition above. 

  1. f(x) = 3n2 + 5n + 2
g(x) = n2


  2. f(x) = n/3 - 4
g(x) = n


  3. f(x) = 5log2(n) 
g(x) = n


  4. f(x) = n2
g(x) = 3n2 + 5n + 2