# TANCET 2011 ALGORITHMS

107 views
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
0
Its option 2.

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

f+g=O(n^2)

f*g=O(n^3)
0

Hemanth_13 why not option 3?

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

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

Option 3 is the right

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.

## Related questions

1
325 views
An array has 5 elements. Calculate the following: SL. NO: NAME ARRAY IS ALREADY SORTED ARRAY IS REVERSE SORTED ELEMENT COMPARSIONS ELEMENT EXCHANGES ELEMENT COMPARISONS ELEMENT EXCHANGES 1 BUBBLE SORT ? ? ? ? 2 SELECTION SORT ? ? ? ? 3 INSERTION SORT ? ? ? ? 4 QUICK SORT ? ? ? ? 5 MERGE SORT ? ? ? ? 6 RADIX SORT ? ? ? ? 7 HEAP SORT ? ? ? ? 8 TREE SORT ? ? ? ? 9 COUNTING SORT ? ? ? ?