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) [TEX]n^{2} + 2n^{3} = O(n^{3}) [/TEX]
[TEX]f(n) = 2n^{3}, g(n)= (n^{3}) [/TEX]
if [TEX]f(n) \in O(g(n))[/TEX]
[TEX]0 \leq f(n) \leq cg(n)[/TEX]
[TEX]0 \leq 2n^{3} \leq c*n^{3} for \ n \geq 0[/TEX]
[TEX]any \ c \geq 2 \ \ f(n) \leq g(n) \ for \ n \geq 0[/TEX]
2)[TEX]2n + n^{2} \neq \Omega (n^{3}) [/TEX]
[TEX]f(n)=n^{2}, g^{3}[/TEX]
[TEX]0 \leq cg(n) \leq f(n)[/TEX]
[TEX]0 \leq c*n^{3} \leq n^{2} \ for \ n \geq 0[/TEX]
[TEX]any \ c \leq \frac{1}{n} \ for \ n \geq 0 [/TEX]
3) [TEX]ln \ n = \Theta (lg \ n) [/TEX]
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?