The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
34 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 by Active (4.9k points) | 34 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.
by Loyal (6.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,788 answers
192,413 comments
90,926 users