1
$\begingroup$

I have a question about Big O notation when it comes to these minimum and maximum functions. I have the following:

$f = max(10^5, \sqrt n)$ and

$g = min(10^8, n log(n))$

I feel that the value of $f$ is $10^5$ because aren't we dealing with a vertical slope that cannot be bound by the square root function? And for $g$, the value should be $n log(n)$ because $10^8$ is not bounded by $n log(n)$.

For this reason, I say that $O(f) = O(10^5)$ and $O(g) = O(n log(n))$. However, I feel like I am not writing the Big O notation of these right, especially with $f$.

I also feel like the following applies and is worth acknowledging for myself:

$g \in O(f)$ is true. However, the vice versa of this is false:

$f \in O(g)$ is false.

Could someone explain to me if I am right about this? Did I write the Big O notation correctly? I am not sure if I am interpreting these correctly.

$\endgroup$
3
  • $\begingroup$ No, it's the exact opposite, $f \in \mathcal{O}(g)$ and $g \not \in \mathcal{O}(f)$. $\endgroup$
    – enedil
    Mar 6, 2019 at 0:37
  • $\begingroup$ Can you explain why? I don't think I understand the relationship maybe. $\endgroup$ Mar 6, 2019 at 0:42
  • $\begingroup$ I'm writing up an answer $\endgroup$
    – enedil
    Mar 6, 2019 at 0:42

1 Answer 1

1
$\begingroup$

I will make my own response because while it seems my definitions are similar to yours, my conclusion is the opposite.

$f(n) = \max(10^5,\sqrt{n})$

$g(n) = \min(10^8,n \log n)$

Since $f$ is a max, then $f(n) = \sqrt{n}$ for all $n \geq 10^{10}$. That makes $f(n) \in O(\sqrt{n})$:

$$O(g(n)) = \{h(n): \text{ there exist positive constants } c, n_0 \text{ such that } 0 \leq h(n) \leq c g(n) \text{ for all } n \geq n_0\}$$

The constant $c=1$ and $n_0 = 10^{10}$.

Since $g(n)$ is a min, once $n$ is large enough $g(n) = 10^8$. In particular, if the log is base 10, when $n \geq 10^7$, $g(n) = 10^8$. This makes $g(n) \in O(1)$, with constant $c=10^8$ and $n_0 = 10^7$.

In fact, $f(n) \in \Theta(\sqrt{n})$ and $g(n) \in \Theta(1)$; this means these bound are asymptotically tight. This notation is defined as follows

$$\Theta(g(n)) = \{h(n): \text{there exist } c_1>0, c_2>0, n_0 \text{ such that } 0 \leq c_1 g(n)\leq f(n)\leq c_2 g(n) \text{ for all } n \geq n_0\}$$

$\endgroup$

You must log in to answer this question.

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