in Algorithms
144 views
0 votes
0 votes
Consider f(n) and g(n) be asymptotic non-negative functions.

So here can we say that min(f(n), g(n)) = Θ(f(n) + g(n))

My proof for this

For f(n) = Θ(g(n))

c1*g(n) $\leq $ f(n)  $\leq $ c2*g(n) such that c1, c2 >0

 

Considering the above definition suppose, f(n) = $n^{2}$ and g(n) = $n^{3}$

min($n^{2}$,  $n^{3}$) = $n^{2}$

Now for this we can write like 0.001*($n^{3}$ + $n^{2}$)  $\leq $ $n^{2}$ $\leq $ 1* ($n^{3}$ + $n^{2}$)

 

So thus we can say that  min(f(n), g(n)) = Θ(f(n) + g(n))

Is this the correct way? What would be the correct answer?
in Algorithms
144 views

3 Comments

$0.001(n^3+n^2) $$\leq$ $n^2$  is this valid for all $n>n_{0}$ ?

If you take $n>999$ then this result is invalid .
2
2
edited by
The actual relation should be max$(f(n),g(n))=\theta(f(n)+g(n))$ .

Can you give a try to prove it ?
0
0
Yes you are right, for all n > 999 the condition is failing. Thank you for your clarification
0
0

Please log in or register to answer this question.