# Homework Help: Big O Notation Proofs

1. Sep 12, 2009

### needhelp83

O-notation
– O(g(n)) = { f (n) : there exist positive constants c and n0 such that
0 ≤ f (n) ≤ cg(n) for all n ≥ n0}
– g(n) is an upper bound of f(n), may not be tight

Ω-notation
– Ω(g(n)) = { f (n) : there exist positive constants c and n0such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n0}
– g(n) is an lower bound of f(n), may not be tight Θ-notation

– Θ(g(n)) = { f (n) : there exist positive constants c1, c2, and n0such
that 0 ≤ c1g(n) ≤ f (n) ≤ c2 g(n) for all n ≥ n0}
– We write f (n) = Θ(g(n)) instead of f (n) ∈Θ(g(n))
– g(n) is an asymptotically tight bound for f(n)

1) $$n^{2} + 2n^{3} = O(n^{3})$$
$$f(n) = 2n^{3}, g(n)= (n^{3})$$
if $$f(n) \in O(g(n))$$
$$0 \leq f(n) \leq cg(n)$$
$$0 \leq 2n^{3} \leq c*n^{3} for \ n \geq 0$$
$$any \ c \geq 2 \ \ f(n) \leq g(n) \ for \ n \geq 0$$

2)$$2n + n^{2} \neq \Omega (n^{3})$$
$$f(n)=n^{2}, g^{3}$$
$$0 \leq cg(n) \leq f(n)$$
$$0 \leq c*n^{3} \leq n^{2} \ for \ n \geq 0$$
$$any \ c \leq \frac{1}{n} \ for \ n \geq 0$$

3) $$ln \ n = \Theta (lg \ n)$$
f(n) = Θ(g(n))
C1lg(n) ≤ ln(n) ≤ C2lg(n)
(1)ln(n) ≤ C2lg(n)
C2 = 1
ln(n) ≤ lg(n)
n = 1
e^x = 1 n^x = 1
x = 0
holds for all n > 0

(2)C1lg(n) ≤ ln(n)
C1 = ½
½lg(n) ≤ ln(n)
n = 1
½(0) ≤ 0
holds for all n > n/2

I am a beginner and looking for feedback. Are there any mistakes I have made or changes that need to be made when proving these?