a) Show that $3x+7$ is $\Theta(x)$.

b) Show that $2x^2 +x -7$ is $\Theta(x^2)$

$2x^2+x-7 \geq x^2$ for $x \geq 2$

if $x \gt 1$

$x^2 \gt x$

$2x^2 \gt 2x$

$x^2 \gt 1$

$x^2\geq x^2$

c) Show that $\lfloor x+.5\rfloor$ is $\Theta(x)$

d) Show that $\log_{10}(x)$ is $\Theta(\log_2(x))$

I'm not very sure about if I'm setting these up the right way and I'm not sure how to start a, c, and d.

  • $\begingroup$ Do you know what it means for a function $f(x)$ to be in $O(g(x))$? If you don't, look up the definition. If you do, then try to apply the definition to, say, your first question. For most of your questions, the proof drops out almost immediately. $\endgroup$ – Rick Decker Nov 14 '14 at 1:09
  • $\begingroup$ I know that the definitions are big Omega: Let f and g be 2 functions from R to R. We say that f(x) is Omega(g(x)) if there exists a positive constant c and a constant k such that Vx>k, |f(x)| > C |g(x)| Big Theta: let f and g be functions from R to R. We say that f(x) is Θ(g(x)) if f is O(g) and f is omega(g). I don't know how to apply it $\endgroup$ – dov rosenfeld Nov 14 '14 at 17:33
  • $\begingroup$ Take a look at my answer. Hope it helps. $\endgroup$ – Rick Decker Nov 14 '14 at 17:46
  • $\begingroup$ It's not clear to me what you're saying in (b); all of the things you say are true (minus the one presumed typo I fixed) but they don't add up to an answer to the question. $\endgroup$ – Steven Stadnicki Dec 8 '14 at 2:04

Here's a sample. To show $3x+7\in \Theta(x)$ we need to show two things:

  1. $3x+7\in O(x)$
  2. $3x+7\in \Omega(x)$

To show (1) we need a $c>0$ and $k$ such that $3x+7<c\,x$ for all $x>k$. Suppose we pick $c=4$, then we need to find when $3x+7<4x$, but that holds whenever $7<x$ so we can use $k=7$.

To show (2) we need a $d>0$ and $k$ such that $3x+7>d\,x$ for all $x>k$. The obvious choice is to pick $d=3$, since it's clear that $3x+7>3x$, for all $x$, so we can use $k=0$ and conclude that $3x+7 > 3x$ for all $x>0$ and we're done.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.