2 votes 2 votes Let f (n) = Ο(n), g(n) = Ο(n) and h(n) = θ(n). Then [f (n) . g(n)] + h(n) is _______. PreSha asked Jan 23, 2018 PreSha 706 views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply akash.dinkar12 commented Jan 23, 2018 reply Follow Share https://gateoverflow.in/11232/let-f-n-ω-n-g-n-o-n-and-h-n-ѳ-n 0 votes 0 votes Anu007 commented Jan 23, 2018 reply Follow Share O(n2) 2 votes 2 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share akash.dinkar12 this is different question 0 votes 0 votes akash.dinkar12 commented Jan 23, 2018 reply Follow Share Oh Yes!! It will be O(n2) 0 votes 0 votes sumit goyal 1 commented Jan 23, 2018 reply Follow Share why not $\Theta (n)$ prove me wrong 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share sumit goyal 1 we know upper bound of f(n) and g(n) so multiplication of f(n) and g(n) will be O(n2) if the equation was f(n) + g(n) + h(n) then we can say Θ(n) 1 votes 1 votes akash.dinkar12 commented Jan 23, 2018 reply Follow Share [f (n) . g(n)] + h(n) [O(n) . O(n) ] + Θ(n) O(n2) + Θ(n) = O(n2) 0 votes 0 votes sumit goyal 1 commented Jan 23, 2018 reply Follow Share $\frac{1}{n} = O(n) , \frac{1}{n } = o(n) , 8n = \Theta (n)$ $f(n) = g(n) = \frac{1}{n}$ $h(n) =8n$ $\frac{1}{n^2} + 8n = \Theta (n)$ since $\frac{1}{n^2}$ is very less compared to 8n i neglected it 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share $f(n)\left\{\begin{matrix} logn & n<20\\ n & n>20 \end{matrix}\right.$ $g(n)\left\{\begin{matrix} n & n>20 \\ loglogn & n<20 \end{matrix}\right.$ f(n).g(n) $\not\equiv \Theta (n)$ 1 votes 1 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share in you example place f(n) = g(n) = n 1 votes 1 votes sumit goyal 1 commented Jan 23, 2018 reply Follow Share @ Mk Utkarsh in my example i took 1/n because then only we can say f(n) = O(n) or 1/n = O(n) 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share so by taking n also we can say that n = O(n) or n $\leq n$ 1 votes 1 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share and then n.n = n2 it cannot go beyond this range of n2 hence O(n2) 1 votes 1 votes sumit goyal 1 commented Jan 23, 2018 reply Follow Share Mk Utkarsh yes thank you 1 votes 1 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share also answer is $\Omega$(n) 1 votes 1 votes MiNiPanda commented Jan 24, 2018 reply Follow Share Yes..Ω(n) I also think the same.. 0 votes 0 votes Please log in or register to add a comment.