Big O of ceil(log_p(n))

Question

I have the function $$f(n) = \lceil \log_p(n) \rceil$$ where $n>0$ and $p \ge 2$. What is the Big O approximation for $n \rightarrow \infty$?

How can I derive it based on the known definition of Big 0?

Answer 1

By the definition of ceiling function,

$$\log_p n \le f(n) < 1 + \log_p n$$

For the case $p > 1$, for large $n > p$, the upper bound is

$$1+\log_p n = \log_p pn < \log_p n^2 = 2\log_p n = \frac{2}{\log p}\log n$$

---

For the case $0 < p < 1$, for large enough $n>\dfrac1p$, $f(n)$ and $(1+\log_p n)$ are negative. So considering the absolute values,

$$|1 + \log_p n| < |f(n)| \le |\log_p n|$$

The upper bound is

$$|\log_p n| = -\log_p n = \frac1{-\log p}\cdot\log n$$

Additionally, for the interest of big-$\Theta$ notation, the lower bound is

$$|1 + \log_p n| = -1-\log_p n = -\log_p pn = \frac{\log pn}{-\log p}$$

For large $n > \frac1{p^2}$, i.e. $p > \frac 1{\sqrt n}$,

$$\frac{\log pn}{-\log p} > \frac{\log \sqrt n}{-\log p} = \frac1{-2\log p} \cdot \log n$$

($-\log p$ is a positive constant)