edited by
3,816 views
4 votes
4 votes

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))$
edited by

3 Answers

Best answer
0 votes
0 votes
2 votes
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 votes
1 votes

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.

Answer:

Related questions

3 votes
3 votes
1 answer
3
go_editor asked Jul 31, 2016
3,262 views
An all-pairs shortest-paths problem is efficiently solved using:Dijkstra's algorithmBellman-Ford algorithmKruskal algorithmFloyd-Warshall algorithm