1

I'm currently working on aysmptotic notation.

I know the basic laws of big theta, O, and omega. But I'm having a little confunsion in understanding simplifying the expressions (if that's even possible).

I'm essentially wondering if the following is true...

Θ(⌈x/4⌉) = Θ(x)

...and if so, I am looking to prove that.

I can show that x is Θ(⌈x/4⌉) and also that ⌈x/4⌉ is Θ(x)

$ $

$0 <= (1)⌈\frac{x}{4}⌉ <= x$

$0 <= x <= (4)⌈\frac{x}{4}⌉$

Hence x is Θ(⌈x/4⌉)

$ $

$0 <= ⌈\frac{x}{4}⌉ <= (1)x$

$0 <= (\frac{1}{4})x <= ⌈\frac{x}{4}⌉$

Hence ⌈x/4⌉ is also Θ(x)

But does this mean that when the cost of a step is Θ(⌈x/4⌉) then that is equivalent of saying the step costs Θ(x)?

Wolff
  • 573

1 Answers1

1

The answer depends on the domain you consider.

Note that $0 \le (1)⌈\frac{x}{4}⌉ \le x$ is in fact not true. Consider $x=1/2$ for example. (Added: it is however true restricted to the natural numbers.)

If you consider the questions for $x \to \infty$ or any domain that is bounded away from $0$ (assuming we are only taking about positive $x$ else some forther consideration is needed) then the answer is affirmative. Since $$x/4 \le ⌈\frac{x}{4}⌉ \le x/4 +1 \le C x $$ for some constant $C$ that can be chosen uniformly for all $x$ if the domain is bounded away from $0$, yet not always.

To reiterate: for $x \to 0$ you do not have the equality as $⌈\frac{x}{4}⌉$ is effectively $1$ then (assuming you consider only positive $x$ at least) and $\Theta(1)$ is not $\Theta(x)$.

quid
  • 42,135
  • Oh, as I should have specified I am working with functions that map the set of natural numbers to the set of real numbers. And my understanding is that f(x) is Big theta, omega, O, etc. if there is some x0 in Natural numbers such that for all x >= x0, the inequality holds, and x0 could be 0 in this case. – Wolff Feb 28 '15 at 15:04
  • Thank you for the clarification this then corresponds to the case "$x \to \infty$" that I disussed. Restricted to the natural numbers your argument is also correct. – quid Feb 28 '15 at 15:07