GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
137 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 

asked in Algorithms by Active (2.4k points)   | 137 views
$\Omega(n)$ ??
Shouldn't at least be of order n³ ?

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

Θ(n2) is waht I got .  

2 Answers

+4 votes
Best answer

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

answered by Veteran (15.4k points)  
selected by

@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 ?

+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*}$$
answered by Veteran (51.4k points)  
  • 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 :(


Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users