2
$\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
$\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$

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.