534 views
3 votes
3 votes

f(n) = $\Theta (n^{2})$  g(n) = $\Omega (n)$  h(n)=O(log n) 

then   [ f(n) . g(n) ] + [h(n) . f(n) ] is 

  • $\Omega (n)$
  • $\Theta (n^{2})$
  • O(log n)

  • None 

1 Answer

3 votes
3 votes
$$\begin{align*} &\Rightarrow T(n) = F(n)*G(n) + H(n)*F(n) \\ &\Rightarrow \text{Given} \;\; F(n) = c.n^2 \\ &\Rightarrow T(n) = \left [ c.n^2*{\color{green}{G(n)}} \right ]_{1st} + \left [ {\color{red}{H(n)}}*c.n^2 \right ]_{2nd} \\ &\Rightarrow T(n) = \left [ c.n^2*{\color{green}{n}} \right ]_{1st-MIN} + \left [ {\color{red}{\log n}}*c.n^2 \right ]_{2nd-MAX} \\ &\Rightarrow T(n) = \left [ c.n^3 \right ]_{1st-MIN} + \left [ c.n^2.{\color{red}{\log n}} \right ]_{2nd-MAX} \\ &\Rightarrow T(n) = \Omega({\color{red}{n^3}}) \\ \end{align*}$$

Related questions

0 votes
0 votes
2 answers
1
PEKKA asked Dec 6, 2016
433 views
Complexity of the following snippet is for (i=1;i<n;++i) for(j=1;j<=n;j=j+i) c=c+1;
1 votes
1 votes
1 answer
2
PEKKA asked Dec 6, 2016
393 views
Complexity of the below code snippet is ..for (i=1;i<=n;++i) { j=2; while(j<=n) { j=j*j; c=c+1; } }$O(nlog n)$$O(n^{2})$$O(nloglog n)$$O(n)$
0 votes
0 votes
1 answer
4
PEKKA asked Dec 5, 2016
325 views
L={ambnckdl | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is best fit under which language classRLDCFLCFLCSL