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)?
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)$.