BIG O NOATION - PLEASE EXPLAIN Let f(n) and g (m) be positive valued increasing

Question

BIG O NOATION - PLEASE EXPLAIN

Let f(n) and g (m) be positive valued increasing functions of n. Using the definition of Big-0, prove that: If f (n) epsilon O (g(m)) and g(n) epsilon O(h (m)) then f(m) E O(h(m)). The definition of f(m) epsilon O(g(n)) says that we can find constants C_1 and k_1 such that whenever n > k_1. Similarly, the definition of g(n) epsilon O(h(n) says that we can find constants C_2 and k_2 such that whenever n > k_2. We can show that f(n) epsilon O(h(n)) by finding constants C_3 and k_3 such that whenever n > k_3. Let C_3 = and let k_3 =. This works because

Explanation / Answer

Hi,

Big O notation is upper bound asymptotic notation that helps in determining the rate of growth of time for an algorithm as the input size increases to a very large value.

As given if f(n)->Og(n) - This means there exists constant c1 and n1 such that f(n)<=c1g(n) for n>=n1

Let f(n) = 3n^2+2n+1 and g(n) = n^2 , then in f(n), 2n can never be greater than 2n^2 and 1 can never be greater than n^2 for n>=1. Hence we can write

f(n)<=8n^2 for n>=1. Here n1=1 and C1=8 .

Also we describe the time complexity of f(n) as O(n^2). It means f(n) will never exceed the rate of growth of function g(n) for some constant c1 and n1 with n>=n1

As per the question since g(n)->Oh(n) -> This implies that h(n) is the tight upper bound for g(n) with some constant c2 and n2 ,hence h(n) would also act as tight upper bound for f(n) too.

Function f(n) would never exceed the rate of growth of time of h(n) for constant c3 and n3 with n>=n3.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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