retagged by
349 views
0 votes
0 votes

Let f (n) = Ο(n), g(n) = Ο(n) and h(n) = θ(n).

Then  [f (n) . g(n)] + h(n) is : a) Ο(n) b)θ(n)


I think it must be 0(n)

retagged by

2 Answers

0 votes
0 votes
this is a repeated question,
still I'll just summarize the concept:
when we say f(n) = O(g(n)), we mean f(n) <= c.g(n) alright ?
and when we say f(n) = Ω (g(n)), then we mean f(n) >=g(n)

So when we say g(n) = max( Ω (n),O(n)), then it can be understood as g(n) <= n or g(n)>=n
clearly g(n) >=n is greater of the two is comes in Ω  ! that's why answer is Ω (n).
0 votes
0 votes

Given, $f(n) = O(n),g(n) = O(n)\ and \ h(n) = \Theta(n)$.

Let $f(n) = O(1) \text{ and } g(n)=O(1) \text{ and $h(n)$ is lower bounded by $cn$}$. Now $f (n).g(n) + h(n) = cn$.

Let $f(n) = c_1n \text{ and } g(n)=c_2n \text{ and $h(n)$ is lower bounded by $cn$}$. Now $f (n).g(n) + h(n) = c_3n^2+c_4n$.

We can see that it's $\color{red}{\Omega(n)}$. But not $o(n)$ or $\Theta(n)$ or $O(n)$ or $\omega(n)$.

Related questions

0 votes
0 votes
1 answer
1
gate_forum asked Jan 13, 2019
471 views
O(n)O(Log n)O(Log log n)none
0 votes
0 votes
1 answer
2
I_am_winner asked Sep 6, 2018
354 views
f(n)>=c1.nh(n)=c2.nthen why answer cant be O(n),It is given as C
3 votes
3 votes
2 answers
3
Rishav Kumar Singh asked Jul 25, 2018
2,982 views
What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.void fun() { int i, j; for (i=1; i<=n; i++) for (j=1; j<=log(i); j...
0 votes
0 votes
2 answers
4
saumya mishra asked Jun 26, 2018
345 views
Explain b and c part???