## 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
```