4 votes

Let $f(n)$ and $g(n)$ be asymptotically non-negative functions. Which of the following is correct?

- $\theta (f(n)^*g(n))=min (f(n),g(n))$
- $\theta (f(n)^*g(n))=max(f(n),g(n))$
- $\theta (f(n)+g(n))=min(f(n),g(n))$
- $\theta (f(n)+g(n))=max(f(n),g(n))$

0 votes

Best answer

2 votes

$f(n)≤f(n)*g(n)\ and\ g(n) ≤ f(n)*g(n)$.

Hence, $max(f(n),g(n)) ∈ O(f(n)*g(n))$

if $f(n)$ or $g(n)$ =0 then $f(n)*g(n) <= max(f(n),g(n))$

Hence, $max(f(n),g(n))∈Ω(f(n)*g(n)$

so $max(f(n),g(n))∈Θ(f(n)*g(n))$ (i`m not sure please correct me if i`m wrong :) )

$f(n)≤f(n)+g(n)\ and\ g(n) ≤ f(n)+g(n)$.

Hence, $max(f(n),g(n)) ∈ O(f(n)+g(n))$ just multiplying a constant,

$f(n)+g(n) ≤ 2* max(f(n),g(n))$. Hence, $max(f(n),g(n))∈Ω(f(n)+g(n))$

Hence, we get that $max(f(n),g(n))∈Θ(f(n)+g(n))$

REF: http://math.stackexchange.com/questions/267252/how-to-prove-that-maxfn-gn-thetafn-gn

1 vote

The Answer should be A is False and B is True.

And the question should be

“Let f(n) and g(n) are asymptotically non negative functions then which of the following is correct:

f(n) * g(n) = theta(max(f(n), g(n))

f(n) + g(n) = theta (max(f(n), g(n))”

Actually, It is not advisable to write Theta (in general any asymptotic notation) on Left Hand Side of any Expression.

Why?? : Suppose it can be written in LHS,

Then, We know x = theta(x),

It means theta(x) = x ---------------- Eq. 1

Also 2x = theta(x),

Then from Eq. 1,

2x = theta(x) = x;

Therefore 2x = x, which gives 2 = 1.

So it can not appear on LHS.

Actually “=theta(.)” defines a binary RELATION between any two functions like a<=b, & writing theta(a) = b is something like writing <a=b, which is weird.

Assuming that your question is:

“Let f(n) and g(n) are asymptotically non negative functions then which of the following is correct:

A. f(n) * g(n) = theta(max(f(n), g(n))

B. f(n) + g(n) = theta (max(f(n), g(n))”

The answer should be A is false in general and B is true.

How B is true ? : For any two asymptotically non negative functions f(n) and g(n),

max(f(n), g(n)) <= f(n) + g(n) <= 2*max(f(n), g(n)), thus for constants c1 = 1, and c2 = 2, f(n) + g(n) will be always bounded by max(f(n), g(n)).

How A is false? : for any f(n) & g(n), three cases are possible:

case 1) when none of the f(n) and g(n) are constant functions - In this case max(f(n) , g(n)) <= f(n) * g(n) so max(f(n), g(n)) can not provide a upper bound for f(n) * g(n).

case 2) when both of the f(n) & g(n) are constant functions or when any one of the f(n) and g(n) is a non zero constant function, In this case f(n) * g(n) = theta(max(f(n), g(n))).

Case 3) when at least any one of the f(n) and g(n) is 0, In this case f(n) * g(n) != theta(max(f(n), g(n))). Since max(f(n), g(n)) COULD BE unable to give a lower bound.