Question

How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound; $$2^x -x^2 < 2^x + x^2 < 2^{x+1} = 2.2^n $$ Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top