search
Log In
0 votes
162 views

Consider the following function $f(x)$ = $x^8$+6$x^7$-9$x^5$-$x^4$+2$x^2$-18. Which of the following is true if x is greater than 56?

  1. $f(x)$ = O($x^8$)
  2. $f(x)$ = Ω($x^8$)
  3. $f(x)$ = θ($x^8$)
  4. $f(x)$ = None of the above.
in Algorithms
edited by
162 views
0

A

we ignore the constants and lower order term. 

what's the answer given?

0
it should be A
0
Should be C as for large enough vale of $x$, $f(x)$ has to be greater than $x^8$ (taking constant as 1 for lower bound).
0
I too think the answer should be A, obviously for the same reason as stated by Utkarsh

But C is provided as answer.
0

 if C is the answer then you cannot say A is wrong 

2
Yes, A isn't wrong. Both A and C are correct - however I assumed that we should give as tight a bound as possible and hence said C is correct.
1
ok i agree with you $C$ is more appropriate
0
A) will be answer

because it can be 57 as lower bound and upperbound $n^{8}$
0

@goxul Please explain me your approach. How C is more appropriate.

1 Answer

1 vote
C is correct because we can find two constants $c_1$ and $c_2$ such that: $c_1 x^8 \leq f(x) \leq c_2 x^8$.

For the LHS to be true, put $c_1 = 1$, RHS will be true for a large value of $c_2$.

Thus we can say that $f(x) \in \Omega(x^8)$

Related questions

1 vote
3 answers
1
189 views
Which of the following is not true in the function $f(n)=2^{n-4}$? $f(n)$=Θ($2^{n+3}$) $f(n)$=Ω($n^{1000}$) $f(n)$=Ο($2^{n-10}$) $f(n)$=$None$
asked Dec 7, 2018 in Algorithms Gupta731 189 views
2 votes
0 answers
3
204 views
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
asked Jan 22, 2018 in Algorithms ashish pal 204 views
...