Suppose f(n) O(g1(n)) and f(n) O(g2(n)). Which of the following are true? Justif

Question

Suppose f(n) O(g1(n)) and f(n) O(g2(n)). Which of the following are true? Justify your answers using the definition of O. Give a counter example if it is false.

Find the order of growth of the following sums.

Suppose f(n) elementof O(g_1(n)) and f(n) elementof O(g_2(n)). Which of the following are true? Justify your answers using the definition of O. Give a counter example if it is false. (a) f(n) elementof O (5 * g_1 (n) + 100) (b) f(n) elementof O(g_1 (n) + g_2(n)) (c) f(n) elementof O (g_1(n)/g_2(n)) (d) f(n) elementof O(max (g_1(n), g_2(n))) Summations Find the order of growth of the following sums. (1) sigma^n_i = 1 (4i + 1). (2) sigma^log_2 (n)_i = 0 2^i (for simplicity you can assume n is a power of 2)

Explanation / Answer

Answer:

3)

d) f(n) belongs to O( max( g1(n), g2(n)))

Let two function f(n) = f1(n) + f2(n)

f1(n) < = c1g1(n) and f2(n) < = c2g2(n) [ as per given conditions

Now , f1(n) + f2(n) < = c1g1(n) + c2g2(n)

< = c1max(g1(n), g2(n)) , c2max(g1(n) , g2(n)

< = (c1 + c2)max(g1(n), g2(n))

< = max(g1(n) , g2(n)) [ c1 + c2 holds because f(n) = f1(n) + f2(n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---