 #1
FritoTaco
 133
 23
 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 bigO.
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?
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 bigO.
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?
Attachments
Last edited: