The Gateway to Computer Science Excellence
+4 votes
1.5k views

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

  1. $\theta (f(n)^*g(n))=min (f(n),g(n))$
  2. $\theta (f(n)^*g(n))=max(f(n),g(n))$
  3. $\theta (f(n)+g(n))=min(f(n),g(n))$
  4. $\theta (f(n)+g(n))=max(f(n),g(n))$
in Algorithms by (111 points) | 1.5k views

3 Answers

0 votes
Best answer
by Loyal (7.3k points)
selected by
+1
i think here no explaination given. then how best answer.
0
link is not working so 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

by Boss (10.5k points)
+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.

by Boss (14.3k points)
Answer:

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,737 questions
57,312 answers
198,342 comments
105,033 users