# Big O notation for min and max functions?

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.

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

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