$\nu(n) = O(\log n)$ I've just started learning asymptotic notation. We say $f(x) = O(g(x))$ if there is a positive constant $A$ such that $|f(x)| \leq Ag(x)$.
An example is then stated: Let $\nu(n)$ be the number of distinct prime factors of a positive integer $n$. Then $\nu(n) = O(\log n)$. How can I prove this?
Attempt:
I need to show $|\nu(n)| \leq A\log n$
My initial thought was the prime number theorem tells us that $\pi(x) \sim \frac{x}{\log x}$ partly as its closely related to $\nu(n)$ and the asymptotic has a logarithm in it, but i'm not really sure how to proceed further or if i'm on the right track?
 A: Remember that for any $n$, we can write the prime decomposition as
$$n = p_1^{a_1}\cdot p_2^{a_2} \cdot p_3^{a_3} \cdots = \prod_{i=1}^k p_i^{a_i}$$
If we define $\nu(n)$ as the number of unique prime factors in $n$, then the upper limit of this product, $k = \nu(n)$.
Every term $p_i^{a_i}$ in the product must be at least $2$. Often they will be much larger, but for our purposes it's enough to write:
$$\forall p_i \mid n, p_i^{a_i} \ge 2 \implies \prod_{i=1}^{\nu(n)} p_i^{a_i} \ge 2^{\nu(n)} \implies n \ge 2^{\nu(n)}$$
Taking the logarithm of this, we have
$$\log n \ge \nu(n) \log 2 \implies \nu(n) \le \frac{\log n}{\log 2} \le A \log n$$
where $A = \log \frac12$. This implies that $\nu(n) = O(\log n)$, as desired.
Note that this is an exceptionally weak upper bound on $\nu(n)$; in fact, equality is true only if $n=2$, and even for relatively small composite numbers, $\nu(n) \ll A \log n$. For instance, if $n=36, \nu(n)=2$, but $\log n / \log 2 = 5.17$. As $\nu(n)$ gets larger, the inequality becomes ludicrously large; using $\#$ as the primorial function, the smallest number with $\nu(n) = 25$ is $97\# \approx 2^{120}$, compared to the lower-bound $2^{25}$.
Since we know that $n\# \sim e^n$, it's possible that $\nu(n) = O(\log \log n)$ or $O(\sqrt{\log n})$ or similar, though I'm uncertain.
