Please solve problems correctly. For each of the following questions, give proof

Question

Please solve problems correctly.

For each of the following questions, give proofs when asked. If you are asked for a proof an answer without will get no marks. You should use the definitions you give in the first two parts of the question. Define what we mean when we write f(n) in omega(g(n)). Define what we mean when we write f(n) in Theta(g(n)). Prove that if f(n) in omega(g(n)) then f(n) nin Theta(g(n)) Is 3n in omega(2n)? Prove your answer. Is n3 in omega(n2)? Prove your answer. Is 3n in omega(2n)? Prove your answer.

Explanation / Answer

1.1)

f(n) = w(g(n))

we mean that the best case complexity of f(n) is g(n)

1.2)

f(n) = theta(g(n))

theta notation is for tighter bound

we mean that the complexity of f(n) is g(n)

1.3)

f(n) = w(g(n))

then we know that best case complexity of f(n) is g(n)

so it can't be f(n) = theta(g(n))

because theta notation is average case but not best case complexity

1.4)

3^n = w(2^n)

this is true

because 3^n best complexity can be 2^n

1.5)

n^3 = w(n^2)

this is true

because n^3 best complexity can be n^2

1.6)

3n = w(2)

this is true

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---