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.
Best Answer
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\}$$