Homework for next class

Tutorial 1

1.8) Use the definition to show, that

f (n) = 2 \cdot 5^{n} + 1000 \cdot n^{4}

is $f (n) \in Θ (5^{n})$ .

Solution We need to show, that

(\exists c_{1}, c_{2} \in R^{+}) (\exists n_{0} \in N) (\forall n > n_{0}) (c_{1} \cdot 5^{n} \leq 2 \cdot 5^{n} + 1000 \cdot n^{4} \leq c_{2} \cdot 5^{n}) .

We can choose $c_{1}$ to be 1, since

5^{n} 0 \leq 2 \cdot 5^{n} + 1000 \cdot n^{4} \leq 5^{n} + 1000 \cdot n^{4} ∣ - 5^{n}

is true for all $n \geq 1$ .

Second part of inequality gives us

2 \cdot 5^{n} + 1000 \cdot n^{4} 1000 \cdot n^{4} \leq c_{2} \cdot 5^{n} \leq (c_{2} - 2) \cdot 5^{n} ∣ - 2 \cdot 5^{n}

If $n^{4} \leq 5^{n}$ , than

1000 \cdot \frac{n ^{4}}{5 ^{n}} \leq 1000 \cdot 1 \leq (c_{2} - 2),

which gives us $c_{2} \geq 1002$ .

Limit: use l’hopital 5 times, eventually we’ll get $1/ 5^{n}$ .

1.9 Let there be three positive functions $f (n)$ , $g (n)$ and $h (n)$ . Prove that

f (n) \in O (g (n)) \land g (n) \in O (h (n)) \Rightarrow f (n) \in O (h (n))

Solution We know, that

(\exists c \in R^{+}) (\exists n_{1} \in N) (\forall n \geq n_{1}) (f (n) \leq c \cdot g (n))

and

(\exists d \in R^{+}) (\exists n_{2} \in N) (\forall n \geq n_{2}) (g (n) \leq d \cdot h (n)) .

Therefore,

f (n) \leq c \cdot g (n) \leq (c \cdot d) \cdot h (n) .

Setting $n_{3} = max {n_{1}, n_{2}}$ and $e = c \cdot d$ gives us

(\exists e \in R^{+}) (\exists n_{3} \in N) (\forall n \geq n_{3}) (f (n) \leq e \cdot h (n)) .

which is exactly the definition of $f (n) \in O (h (n))$ .

1.10 Prove following: Let the $f_{1} (n)$ , $f_{2} (n)$ and $h (n)$ be non-negative functions, such that

f_{1} (n) \in Θ (h (n)) \land f_{2} (n) \in Θ (h (n) \cdot lo g_{2} n)

then $(f_{1} + f_{2}) (n) \in Θ (h (n) lo g_{2} n)$

Solution Sum of functions is defined as

(f_{1} + f_{2}) (n) = f_{1} (n) + f_{2} (n) .

We know that

(\exists c_{1}, c_{2} \in R^{+}) (\exists n_{0} \in N) (\forall n > n_{0}) (c_{1} \cdot h (n) \leq f_{1} (n) \leq c_{2} \cdot h (n)) .

and

(\exists d_{1}, d_{2} \in R^{+}) (\exists n_{1} \in N) (\forall n > n_{1}) (d_{1} \cdot h (n) lo g_{2} n \leq f_{2} (n) \leq d_{2} \cdot h (n) lo g_{2} n) .

meaning that

f_{1} (n) + f_{2} (n) \leq (c_{2} \cdot h (n)) + (d_{2} \cdot h (n) \cdot lo g_{2} n))

f_{1} (n) + f_{2} (n) \leq (c_{2} + d_{2} \cdot lo g_{2} n) \cdot h (n)

Since $lo g_{2} (n) \geq 1$ for $n \geq 2$ ,

(c_{2} + d_{2} \cdot lo g_{2} n) \cdot h (n) \leq (c_{2} + d_{2}) \cdot lo g_{2} (n) \cdot h (n)

is truth.

f_{1} (n) + f_{2} (n) \geq c_{1} \cdot h (n) + d_{1} \cdot lo g_{2} n \cdot h (n)

removing $c_{1} \cdot h (n)$ lowers the right side of the inequality, since all the terms are positive. Thus

f_{1} (n) + f_{2} (n) \geq d_{1} \cdot lo g_{2} n \cdot h (n) .

Together, we get

(\exists e_{1}, e_{2} \in R^{+}) (\exists n_{2} \in N) (\forall n > n_{2}) (e_{1} \cdot h (n) lo g_{2} n \leq (f_{1} + f_{2}) (n) \leq e_{2} \cdot h (n) lo g_{2} n),

where $e_{1} = d_{1}$ , $e_{2} = c_{2} + d_{2}$ and $n_{2} = max {n_{0}, n_{1}, 2}$ . Which is by definition what we wanted to prove.