- #1

FritoTaco

- 132

- 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 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?

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?

#### Attachments

Last edited: