retagged by
516 views
2 votes
2 votes
If f(n)=O(g(n)).  && g(n) != O(f(n))

g(n) = O(h(n)).    && h(n) = O(g(n))

Check following statement are true/false?

1. f(n)+h(n)=theta(g(n))

2. f(n)*h(n)=theta(g(n)*h(n))

3. g(n)*f(n)=big omega(h(n)*f(n))

4. h(n)+g(n) = O(f(n))
retagged by

3 Answers

1 votes
1 votes

 Given f(n)=O(g(n)).  && g(n) != O(f(n))

g(n) = O(h(n)).    && h(n) = O(g(n))

From given information we can conclude f(n)<g(n)=h(n)

Based on it

1. f(n)+h(n)=theta(g(n)) True

2. f(n)*h(n)=theta(g(n)*h(n)) False

3. g(n)*f(n)=big omega(h(n)*f(n)) True

4. h(n)+g(n) = O(f(n)) False

edited by
0 votes
0 votes

From Given assymptotic relation you can conclude that

f(n)<g(n)=h(n)  

Try to put some constant value in place of f(n),g(n) and h(n) Based on which only third option is true as 2*1=big omega(2*1) TRUE. 

0 votes
0 votes

Base on the given question i can deduce than f(n)<{g(n)=h(n)}

lets take an instance of three and solve the question : 

let f(n)=logn,g(n)=n,h(n)=n;

1. f(n)+h(n)=theta(g(n))                    ==>              n+logn = n ? correct SO TRUE        

2. f(n)*h(n)=theta(g(n)*h(n))             ==>              n*logn = n*n ? nopes nlogn != nSO FALSE  

3. g(n)*f(n)=big omega(h(n)*f(n)    ==>              n*logn <= n*logn ? correct make c=2 ! SO TRUE 

4. h(n)+g(n) = O(f(n))                  ==>              n+n <= logn ? nopes it should be small omega! SO False 

No related questions found