For questions 1 and 3 proceed as follows: 1, First explain what needs to be prov

Question

For questions 1 and 3 proceed as follows: 1, First explain what needs to be proven: "We need to find constants c 0 and no 1 integer such that ..." 2. For question 3 use the definition of "big Oh" to explain what it means for f(n) to be O(g(n)) and for g(n) to be O(h(n)). 3. Simplify the above inequalities. 4. Determine the values for c and no For question 2, if you use a proof by contradiction: . First give the claim that you will assume false and from which you will derive a contradiction . Perform steps 1 and 3 as above » Derive a contradiction. 1. (3 marks) Use the definition of "big Oh" to prove that 4/n is O(1). 2. (3 marks) Use the definition of "big Oh" to prove that 2n is not O(1/n) 3. (3 marks) Let f(n), g(n), and h(n) be non-negative functions such that f(n) is O(g(n)) and g(n) is O(h(n)). Use the definition of "big Oh" to prove that f(n) +g(n) is O(h(n)).

Explanation / Answer

Answer 1:

4/n is O(1)

We know the definition of big O:

if f(n) = O(g(n)) , iff

f(n) < = c*g(n)

Here f(n) = 4/n

g(n) = 1

let c = 10 , n = 1

then , f(n) < = c*g(n) = 4/n < = 20*1

n = 1 , therefore 4/1 < = 20

4 < 20 is true as per big O definition

thus 4/n = O(1) is true

Answer 2:

2n is not O(1/n)

We know the definition of big O:

if f(n) = O(g(n)) , iff

f(n) < = c*g(n)

Here f(n) = 2n

g(n) = 1/n

let c = 1 , n = 2

then , f(n) < = c*g(n) = 2n < = c*1/n

n = 1 , therefore 2 < = 1/2*1

2 > 1/2 is false as per big O definition

Thus we can say 2n is not O(1/n) at n = 2 , c = 1

Answer 3:

f(n) + g(n) = O(h(n))

As per definition of big O

f(n) = O(g(n)) iff

f(n) < = c*g(n))

where c is constant

Here f(n) + g(n) = O(h(n))

which means f(n) + g(n) < = c*h(n)

Let f(n) = 2 = g(n) and c = 10 , h(n) = 2

then f(n) + g(n) = c*h(n)

2 + 2 < = 10*2

4 < 20 is true as per big O definition

Thus f(n) + g(n) = O(h(n))

DEAR PLEASE DO RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

WE ARE RESTRICTED TO ANSWER MORE THAN ONE QUESTIONS POSTED TOGETHER. KINDLY POST SEPARATELY TO GET ANSWERED.

THANK YOU!!

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.