TANCET 2011 ALGORITHMS

Question

Suppose f, g, h, k : N → N. If f = O(h) and g = O(k), then

1) f + g = O(h + k)

2) fg = O(hk)

3) Both 1 and 2

4) None of the above

Comments

Its option 2.

f=O(n),g=O(n^2)

f+g=O(n^2)

f*g=O(n^3)

---

Hemanth_13 why not option 3?

since O(n^2) = O(n^2 + n)

---

Yes it is O(h+k) as well but not O(h) + O(k)

Option 3 is the right

Answer 1

Given that:

$f = O(h)$ and $g =O(k)$

This implies that $f  \leq c_1h$ and $g \leq c_2k$.

Let $c_3= max(c_1, c_2)$.

$f + g = c_1h + c_2k \rightarrow f + g = c_3(h + k) \rightarrow f + g \in O(h+k)$.

This is true since we can replace $c_1$ and $c_2$ by $c_3$ while still maintaining the upper bound.

The same logic can apply for $fg$ also.