I have been tasked with proving whether or not the following statements are true or false:
- $\sqrt{n}+7n\cdot\log(n) \in O(n^{2})$
- $\sqrt{n}\in\Theta(n^{2})$
My solutions for both are below.
Solution 1:
With the formal definition of $f(n)\in O(g(n))$ being:
$\exists c\gt0,\ n_{0}\geq0\ \forall n\geq n_{0} :f(n)\leq c\cdot g(n) $
I used $c=7$, $n_{0}=1$. For the first value of $n$; $n = 1$, the definition is met:
$0\leq \sqrt{1}+7(1)\cdot \log(1) \leq 1^{2}\cdot 7$
It is also met with other values of $n$, such as 4 and 100 respectively:
$0\leq \sqrt{4}+7(4)\cdot \log(4) \leq 4^{2}\cdot 7$
$0\leq \sqrt{100}+7(100)\cdot \log(100) \leq 100^{2}\cdot 7$
Thus the statement $\sqrt{n}+7n\cdot\log(n) \in O(n^{2})$ is true.
Solution 2:
With the formal definition of $f(n)\in \Theta(g(n))$ being:
$\exists c_{1}\gt 0, c_{2}\gt 0, n_{0}\geq 0\ \forall n \geq n_{0} : c_{1}\cdot g(n) \leq f(n)\leq c_{2}\cdot g(n)$
I first focused on $\sqrt{n}\in O(n^{2})$, which I showed using $c_{2}=2$, $n_{0}=0$, despite it being quite obvious that bound can never be exceeded. As for $\sqrt{n} \in \Omega(n^{2})$, I chose $c_{1}=1$ and plugged in various values of $n$ showing that $g(n)$ will always exceed $f(n)$, making the statement false.
Although I'm fairly confident in my consclusions, I feel like my solutions and method of "proof" is very naive and unpolished, and I'm wondering if there is possibly a clearer or more elegant way of proving this which isn't just my method of plugging in values chosen arbitrarily (There was no logic behind choose $c$ and $n_0$, I just chose them on a whim).
Both "proofs" are actually no proofs, albeit your conclusions are correct. Here is why:
Solution 1. Showing that an inequality is true for some particular values of $n$ does not constitute a proof of the inequality. You would either need to do a proof by induction (you have already verified the initial condition), or use what you know (if allowed) about basic functions: $$\sqrt n + 7n\log n \le n + 7n\cdot n \le n^2 + 7n^2 \le 8n^2,$$ where we use that $\sqrt n \le n$ and $\log n \le n$ for $n\in\mathbb N^*$.
Solution 2. If you want to show that the presumed asymptotic behaviour is not true, it is not enough for you to find a counterexample for particular values of $c_1, c_2$. You are right about the intuition that the lower bound will be the problem. To actually show this, you want to show that there is no $c_1$ (at all) such that $c_1 n^2 \le \sqrt n$ for all $n$.
Since $\sqrt n \le n$ for all $n$, we look at $c_1 n^2 \le n$ instead. This is equivalent to $c_1 \le \frac 1n$. The right hand side tends to zero as $n\to \infty$, so the largest $c_1$ that satisfies the inequality for all $n\in\mathbb N$ will be $c_1=0$, which contradicts the assumption $c_1 > 0$.
Having shown that there is no $c_1 > 0$ such that $c_1 n^2 \le n$ for all $n$, the even stricter inequality $c_1 n^2 \le \sqrt n$ will not hold for all $n$ and any $c_1>0$ either.