Answer to Question #260074 in Algorithms for anju

Question #260074

Prove that max( f(n), g(n) ) = Ө ( f(n) + g(n) )


1
Expert's answer
2021-11-02T14:43:24-0400

We know that,


f(n)f(n)+g(n)f(n)\le f(n)+g(n)


and g(n)f(n)+g(n)g(n)\le f(n)+g(n)


Now, max(f(n),g(n))O(f(n)+g(n))max(f(n),g(n))\in O(f(n)+g(n))


f(n)+g(n)2max(f(n),g(n))\Rightarrow f(n)+g(n)\le 2max(f(n),g(n))

Hence, max(f(n),g(n))2max(f(n),g(n))max(f(n),g(n))\le2max(f(n),g(n))

max(f(n),g(n))Ω(f(n)+g(n))\Rightarrow max(f(n),g(n)) \in \Omega(f(n)+g(n))

max(f(n),g(n))θ(f(n)+g(n))\Rightarrow max(f(n),g(n))\in \theta(f(n)+g(n))

Hence, we can conclude that

max(f(n),g(n))=θ(f(n)+g(n))max(f(n),g(n))=\theta(f(n)+g(n))


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment