Algorithms Questions

Question

f(n)>=c1.n

h(n)=c2.n

then why answer cant be O(n),It is given as C

Comments

https://gateoverflow.in/11232/let-f-n-%CF%89-n-g-n-o-n-and-h-n-%D1%B3-n

Similar question. Please read comments of this answer, they are very helpful.

---

f(n) +g(n) =max(f(n), g(n) ) - - property

Now for fn lower bound is given means at least value is given not max so the max value could be n^n

But for hn it clear that it couldn't go beyond n..

Now it's quite clear that it depends on fn

Moreover why we can't  take O(n) is bcs it could be more than that of this....

I hope u get ..

Answer 1

f(n) = omega (n) which means  f(n) >=n   [ f(n) should be either n or more than n ]   ['n' , 'n+1' , 'n+2'......]

g(n) = O(n) which means g(n) <=n             [ g(n) should be either n or less than n ]    [ '1' , '2' , '3' ........ 'n']

h(n) =  which means h(n)  = n                   [h(n)  and n both are equal]   ['n']

since f(n) + g(n) >= n

therefore f(n) + g(n) = omega(n)