145 views

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

$\Omega(n)$ ??
Shouldn't at least be of order n³ ?

@Debashish_Deka answer is given as  Ω(n)  but How ?

Θ(n2) is waht I got .

f(n) = n2
g(n) = n
h(n) = 1

[f(n).g(n)]+[h(n).f(n)]  is
=  n3  + n2 = O(n3)

f(n) = n2
g(n) = n4
h(n) = 1
[f(n).g(n)]+[h(n).f(n)]  is
n2*n4   + n2  = O(n6)
Tightest upper Bound is n3  hence Omega(n3

selected

@vijay h(n) is log n  , How u took it as 1 ?

How to find

• f(n).g(n)
• f(n)+g(n)
• f(n) / g(n)

in general ?

h(n) = O(logn)  hence h(n)<=c.logn i took O(1) to get minimum possible case

didn't get  you .
Do u mean h(n) is O( 1) ?

Can u also pls tell  How to find

• f(n).g(n)
• f(n)+g(n)
• f(n) / g(n)

in general ?

\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*}
• What is 1st MIN 2nd MAX denote ?
• Why it is $\Omega(n^{3})$ and Not $O(n^{3})$ or $\Theta(n^{3})$
• 1st_MIN means 1st term minimim bound
• $\Omega(n)$ .etc...you please refer complexity theory
I couldn't understand :(