CODEWITHSUNDEEP
complexity-theory
user2213470
user2213470

Reputation: 89

Time complexity and proof of time complexity

Which is true and which false? I can't really decide which one is true and which false. Maybe in first 3 cases.

  1. 3n^5 − 16n + 2 ∈ O(n^5)
  2. 3n^5 − 16n + 2 ∈ O(n)
  3. 3n^5 − 16n + 2 ∈ O(n^17)
  4. 3n^5 − 16n + 2 ∈ Ω(n^5)
  5. 3n^5 − 16n + 2 ∈ Θ(n^5)
  6. 3n^5 − 16n + 2 ∈ Θ(n)
  7. 3n^5 − 16n + 2 ∈ Θ(n^17)

and how to prove this one:

2^(n+1) ∈ O(3^n/n )

Upvotes: 0

Views: 965

Answers (1)

Kwariz
Kwariz

Reputation: 1316

Back to the definitions, with f and g two positive functions :

f∈𝛰(g) ⇔ ∃k,n₀∈ℕ      ∀n>n₀                f(n) ≤ k.g(n)
f∈𝛺(g) ⇔ ∃k,n₀∈ℕ      ∀n>n₀    k.g(n) ≤ f(n)
f∈𝛩(g) ⇔ ∃k₁,k₂,n₀∈ℕ ∀n>n₀  k₁.g(n) ≤ f(n) ≤ k₂.g(n)

It's easy to see that : f∈𝛰(g) and f∈𝛺(g) implies f∈𝛩(g)

Using these definitions it is easy to prove that 1,3,5,6 are true and that 2 and 7 are false; then 1 and 5 true implies 4 true.

for 2^(n+1) ∈ O(3^n/n ) :
can you prove lim 2^(n+1)/ ( 3^n/n ) = 0 when x→+∞ ?
If so, you proved that for all ε>0 there exists δ such that for all n>δ we have 2^(n+1)/(3^n/n)<ε
For ε=2, there exists n₀ such that for all n>n₀ 2^(n+1)<2.3^n/n
what can you conclude ?

Upvotes: 2

Related Questions