retagged by
345 views

1 Answer

Best answer
0 votes
0 votes

Let us think about the possible minimum value of  "g(n)  -  h(n)" .. 

Let g(n)  =  2n

     h(n)   =  2n   ..Both are valid functions as  2n = O(n)  =  Ω(n)

Now  g(n)  -  h(n)    =  2n  -  2n  =   0  [means a constant]

Means  minimum value of  g(n)  -  h(n) may be a constant as well..

Hence in that case f(n) will be dominating as  f(n)  =  θ(n) ...

Now  let g(n)  =  n3    h(n)  =  n

Hence  g(n)  -  h(n)    =  n3  - n  which is asymptotically larger than  n..Hence in this case  "g(n) - h(n)" will dominate over f(n) ..

So we see in any case we wont get less than order than n..In the first case due to first term we are getting a function of n and in the second case larger than function of n..

Hence lower bound is function of n..

Hence f(n) + g(n) - h(n)   =   Ω(n)

selected by