0 votes 0 votes 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? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above. Algorithms gateforum-test-series algorithms asymptotic-notation + – Gupta731 asked Dec 7, 2018 • edited Mar 15, 2019 by ajaysoni1924 Gupta731 702 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Mk Utkarsh commented Dec 7, 2018 reply Follow Share A we ignore the constants and lower order term. what's the answer given? 0 votes 0 votes anjali007 commented Dec 7, 2018 reply Follow Share it should be A 0 votes 0 votes goxul commented Dec 7, 2018 reply Follow Share 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 votes 0 votes Gupta731 commented Dec 7, 2018 reply Follow Share I too think the answer should be A, obviously for the same reason as stated by Utkarsh But C is provided as answer. 0 votes 0 votes Mk Utkarsh commented Dec 7, 2018 reply Follow Share goxul if C is the answer then you cannot say A is wrong 0 votes 0 votes goxul commented Dec 7, 2018 reply Follow Share 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. 2 votes 2 votes Mk Utkarsh commented Dec 7, 2018 reply Follow Share ok i agree with you $C$ is more appropriate 1 votes 1 votes srestha commented Dec 7, 2018 reply Follow Share A) will be answer because it can be 57 as lower bound and upperbound $n^{8}$ 0 votes 0 votes Gupta731 commented Dec 7, 2018 reply Follow Share @goxul Please explain me your approach. How C is more appropriate. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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)$ goxul answered Dec 7, 2018 goxul comment Share Follow See all 0 reply Please log in or register to add a comment.