Big O Notation Proofs: O, Ω, and Θ

[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?

 

[Valkarie]

Your proof looks correct. It is always a good idea to double check your answer to make sure you have not made any mistakes. Additionally, it might be helpful to include a brief explanation of each step in the proof to provide additional clarity.

 

[Mene]

I would like to commend your efforts in understanding and explaining the concepts of Big O, Ω, and Θ notations. Your proofs are clear and well-organized, and you have correctly identified the key components in each notation.

However, there are a few points that I would like to clarify and provide feedback on:

1) In your first proof, you have correctly shown that f(n) = 2n^3 is in O(n^3) by choosing c = 2. However, it is important to note that c must be a positive constant, so c = 2 is just one possible choice. Other values of c, such as c = 3 or c = 10, would also satisfy the condition 0 ≤ 2n^3 ≤ cn^3 for all n ≥ 0. Therefore, it would be more accurate to say "any c ≥ 2" instead of "any c ≥ 0" in your proof.

2) In your second proof, you have correctly shown that f(n) = n^2 is not in Ω(n^3) by choosing c = 1/n. However, it is important to note that c must be a positive constant, so c = 1/n is not a valid choice. Instead, you could choose c = 1, which would satisfy the condition 0 ≤ cn^3 ≤ n^2 for all n ≥ 0. Therefore, it would be more accurate to say "any c ≤ 1" instead of "any c ≤ 1/n" in your proof.

3) In your third proof, you have correctly shown that ln(n) is in Θ(lg(n)) by choosing c1 = 1/2 and c2 = 1. However, it is important to note that c1 and c2 must be positive constants, so c1 = 1/2 is not a valid choice. Instead, you could choose c1 = 1, which would satisfy the first inequality ln(n) ≤ lg(n) for all n > 0. Similarly, c2 must also be a positive constant, so c2 = 1 is a valid choice, but you could also choose a larger value such as c2 = 2. This would satisfy the second inequality lg(n) ≤ ln(n) for all n > 1. Therefore, it would be more accurate to say "any c1 ≥