0 votes 0 votes 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 Algorithms tancet asymptotic-notation + – Balaji Jegan asked Oct 23, 2018 • retagged Jun 26, 2022 by makhdoom ghaya Balaji Jegan 513 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Hemanth_13 commented Oct 23, 2018 reply Follow Share Its option 2. f=O(n),g=O(n^2) f+g=O(n^2) f*g=O(n^3) 0 votes 0 votes Balaji Jegan commented Oct 23, 2018 reply Follow Share Hemanth_13 why not option 3? since O(n^2) = O(n^2 + n) 0 votes 0 votes Hemanth_13 commented Oct 23, 2018 reply Follow Share Yes it is O(h+k) as well but not O(h) + O(k) Option 3 is the right 0 votes 0 votes Please log in or register to add a comment.
0 votes 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. goxul answered Oct 24, 2018 goxul comment Share Follow See all 0 reply Please log in or register to add a comment.