search
Log In
4 votes
2.2k 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
edited by
2.2k views

3 Answers

0 votes
 
Best answer

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

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.

Answer:

Related questions

2 votes
2 answers
1
3.5k views
Given the symbols A, B, C, D, E, F, G and H with the probabilities$\frac{1}{30}, \frac{1}{30}, \frac{1}{30}, \frac{2}{30}, \frac{3}{30}, \frac{5}{30}, \frac{5}{30}$ and $\frac{12}{30}$respectively. The average Huffman code size in bits per symbol is $\frac{67}{30}$ $\frac{70}{34}$ $\frac{76}{30}$ $\frac{78}{30}$
asked Aug 2, 2016 in Algorithms jothee 3.5k views
3 votes
1 answer
2
2.4k views
Which of the following statements is true for Branch-and-Bound search? Underestimates of remaining distance may cause deviation from optimal path Overestimates can't cause right path to be overlooked Dynamic programming principle can be used to discard redundant partial paths All of the above
asked Aug 1, 2016 in Algorithms jothee 2.4k views
3 votes
1 answer
3
1.7k views
An all-pairs shortest-paths problem is efficiently solved using: Dijkstra's algorithm Bellman-Ford algorithm Kruskal algorithm Floyd-Warshall algorithm
asked Aug 1, 2016 in Algorithms jothee 1.7k views
0 votes
1 answer
4
2.7k views
The travelling salesman problem can be solved in Polynomial time using dynamic programming algorithm Polynomial time using branch-and-bound algorithm Exponential time using dynamic programming algorithm or branch-and-bound algorithm Polynomial time using back tracking algorithm
asked Jul 12, 2015 in Algorithms Shubham Sahu 2.7k views
...