We know that,
f(n)≤f(n)+g(n)
and g(n)≤f(n)+g(n)
Now, max(f(n),g(n))∈O(f(n)+g(n))
⇒f(n)+g(n)≤2max(f(n),g(n))
Hence, max(f(n),g(n))≤2max(f(n),g(n))
⇒max(f(n),g(n))∈Ω(f(n)+g(n))
⇒max(f(n),g(n))∈θ(f(n)+g(n))
Hence, we can conclude that
max(f(n),g(n))=θ(f(n)+g(n))
Comments
Leave a comment