GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
121 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.3k points)   | 121 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 (14.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 (41.1k 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 :(

Related questions

Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users