I need help confirming that my way of proof is alright. This is my first class in algorithms so I just wanna know if I’m on the right track. :)
Problem $\boldsymbol{\#1}$
(a) $C(n) =\log(n^n)$ implies that $C(n)$ is $\Theta(\log n)$.
Definition of Theta notation:
$f$ is of order $g$, writen “$f(x)$ is $\Theta(g(x))$”, if and only if there exist positive real numbers $A$, $B$ and a nonnegative real number $k$ such that: $$A|g(x)| \leq |f(x)| \leq B|g(x)| \text{ for all real number } x \geq k.$$
Proof:
So in order for “$C(n) =\log(n^n)$ is $\Theta(\log n)$” to be true we must satisfy the following inequality for some $k$, $A$ and $B$:
$$A|\log n| \leq \log(n^n) \leq B|\log n| \text{ for all real number } x>9.$$
By rule of logs. and we can drop the abs. signs because it’s implies we are dealing with positive numbers:
$$A \log n \leq n \log n \leq B \log n; \\ A \leq n \leq B.$$
Looking at RHS equation let’s assume $n \geq 1$.
For $n \leq B$, there is no $B$ that can satisfy this inequality because $n$ can grow arbitrary large but $B$ remains a constant.
We don’t have to check the other side of the inequality because to be in $\Theta$ both sides must be true.
We also know by the L’Hopital’s rule that the rate of growth of $n \log n$ is much faster to be only at most $\log n$ so since it fails “$C(n)$ is $O(\log n)$” it can’t possibly be $\Theta(\log n)$ since another fact that must be true for “$C(n)$ is $O(\log n)$” to be true is:
$f(x)$ is $\Omega(g(x))$ and $f(x)$ is $O(g(x))$ if and only if $f(x)$ is $\Theta(g(x))$.
L’Hopital’s rule: $$\lim_{n\to\infty} \frac{\log(n^n)}{\log n} = \frac{n \require{cancel} \cancel{\log n}}{\cancel{\log n}} = n \to \infty.$$ The top function grows faster. So the statement is always false.
$\log(n) \notin \Theta(\log(n^n))$
You can prove this fairly easy. If you know how logarithms work, you can do the following: $\log(n^n) = n\log(n)$ and that is obviously not in $\Theta(\log(n))$ since it grows $n$-times as fast.
$f(n) \in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$.
But in this case $\log(n) \notin \Omega(n\log(n))$ (you can prove this from the definition).
You did this in your proof, so I guess you got the idea.