search
Log In
0 votes
71 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
in Algorithms 71 views
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

1 Answer

0 votes
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

0 votes
0 answers
1
270 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 ? ? ? ?
asked Oct 24, 2018 in Algorithms Balaji Jegan 270 views
0 votes
2 answers
2
223 views
A man alternately tosses a coin and throws a dice, beginning with the coin. Then probability that he will get a head before he gets a 5 or 6 on dice is 1) 1/4 2) 3/4 3) 4/5 4) 4/7
asked Oct 24, 2018 in Probability Balaji Jegan 223 views
0 votes
1 answer
3
65 views
If mean = (3 median – mode)x, then value of x is 1) 1 2) 2 3) 1/2 4) 3/2
asked Oct 24, 2018 in Probability Balaji Jegan 65 views
0 votes
0 answers
4
285 views
Minimum Hamming distance method is used for correction of 1) syntactic errors 2) semantic errors 3) algorithmic errors 4) transcription errors
asked Oct 24, 2018 in Computer Networks Balaji Jegan 285 views
...