Big O/Little O, Big Ω, little ω

[FritoTaco]

Homework Statement:

For each pair of functions below, list which one(s) of the following are true:
$(1) f(n)=o(g(n)), \\ (2) f(n) = O(g(n)), \\ (3) f(n) = \Theta(g(n)), \\ (4) f(n) = \Omega(g(n)),\\ (5) f(n) = \omega(g(n)).$

$f(n)=\log(n+5), g(n)=\log(25n^2)$

Relevant Equations:

let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real numbers.

$f(n)∈O(f(n))$ if there exist positive constants $c$ and $n_0$ such that:
$f(n) \leq c \cdot g(n)$ for all $n > n_0$

$f(n)∈\Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that:
$f(n) \geq c \cdot g(n)$ for all $n > n_0$

$f(n)∈ \theta(g(n))$ iff $f(n)∈ O(g(n))$ and $f(n) ∈ \Omega(g(n))$
$f(n) ∈ o(g(n))$ iff $f(n) ∈ O(g(n))$ and $f(n) ∉ \theta(g(n))$
$f(n) ∈ \omega(g(n))$ iff $f(n) ∈ \Omega(g(n))$ and $f(n) ∉ \theta(g(n))$

Just by looking at the two functions $f(n)$ and $g(n)$, I can see that $f(n)$ is smaller
than $g(n)$ because of $n^2$. To prove this. I attempted the following and I'm not sure
if I'm right.

$log(n+5) \leq c \cdot log(25n^2)$ for all $n \geq n_0$
$log(n+5) \leq c * log(25) + log(n^2)$
$log(n+5) \leq c * log(25) + 2 \cdot log(n)$

A quick note:
$log(n+5) \leq 2 \cdot log(n)$
$0 \leq log(25)$

$log(n+5) + 0 \leq 2 \cdot log(n) + log(25)$

$c = 2$
$n_0 = 1$

Therefore, $log(n+5) ∈ O(log(25))$


That's my attempt to show it is big-O.
I'm not sure how to solve for $\Omega$,
but my attempt is the same as the above.

$log(n+5) \geq log(25n^2)$ for all $n \geq n^0$

i can't simplify $log(n+5)$

$c \cdot log(n+5) \geq log(25n^2)$

$c = 1$
so I pick a $c$ value and try to find a $n_0$
such that $1 \cdot log(n+5) \geq log(25n^2)$

I'll pick $n_0 = 10$

$1 \cdot log(10+5) \geq log(25(10^2))$

this is false. But I don't understand how to conclude
that $log(10+5) ∈ \Omega(log(25(10^2)))$
is false (which I assume it is false). Then I have no idea
how to begin to prove $f(n) ∈ o(g(n))$. I've been given
an example like this:

$3n ∈ o(n^2)$ because $n < n^2$ but,
$3n^2 ∉ o(n^2)$ because $n^2 \nless n^2$.
Do I have to do a new proof or can I just use $n_0 = 1$
and plug it into $f(n)=log(n+5))$ and $g(n)=log(25n^2)$?
Also, is my $c$ correct for the first proof?

 

[mfb]

$log(n+5) \leq c * log(25) + log(n^2)$

Here a factor c got lost.

$log(n+5) ∈ O(log(25))$

Huh? No. $log(n+5) ∈ O(log(25n^2))$ but that is coming from the n^2 term, the 25 doesn't play a role.

In the first formula for Ω there is a c missing.

$1 \cdot log(10+5) \geq log(25(10^2))$ is false

That just tells you that n0=10 or c=1 (or both) are too small.

For large n the +5 becomes negligible (this a heuristic argument here). What does that mean for the ratio of the two functions? Does that give you an idea which c to study? That you can formalize then.