3
$\begingroup$

I want to calculate the big-O notation for ceiling and floor functions such as $f(x)= \lfloor x^{\frac{4}{3}} \rfloor$ and $f(x)=x \lceil \frac{n}{2} \rceil $
the domain of these functions is $\mathbb{N}^*$.

in the first function can we ignore the floor rounding and treat it as $f(x)= x^{\frac{4}{3}} $ then $f(x)$ is $O(x^{\frac{4}{3}})$ ?
I've never seen fractions in the power of so I'm not sure if $O(x^{\frac{4}{3}})$ is true or it should simply be $O(x^2)$ ?
I know we can ignore constants but never seen an example with a fraction as the power of

for the second function I figured we can also ignore the ceiling rounding so the function becomes $f(x)=x \frac{x}{2} $ and then we ignore the denominator so, $f(x)$ is $O(x^2)$

Also I want to verify if we can ignore the ceiling since big-O is used for big numbers and a ceiling/floor won't make any difference when we're dealing with really big numbers

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, you are right. $f(x)$ is $O(x^{4/3})$ is equivalent to the statement that there exist positive constants $C, x_0$ such that $|f(x)| \le Cx^{4/3}$ for all $x\ge x_0$. We can write $$f(x) = \lfloor x^{4/3} \rfloor = x^{4/3} + g(x),$$ where $g(x)$ is bounded in absolute value by $1$. Hence $|f(x)| \le |x^{4/3}| + 1 \le 2|x^{4/3}|$ for $x \ge 1$. So, $f(x)$ is indeed $O(x^{4/3})$.

Similarly,

$f(x) = x\lceil \frac{x}{2}\rceil = x(\frac{x}{2} + O(1))=\frac{x^2}{2} + O(x) = O(x^2)$. ($O(1)$ stands for a function that is bounded in absolute value. In this case, that function is bounded by $1$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .