Big O/Little O, Big Ω, little ω

  • Comp Sci
  • Thread starter FritoTaco
  • Start date
In summary, the conversation discusses how to prove that f(n) is smaller than g(n) using the big-O notation and how to find the correct values for c and n0. The first attempt is incorrect due to a missing factor and the second attempt is also incorrect due to the +5 becoming negligible for large n. A heuristic argument is suggested to find the correct values for c and n0.
  • #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?
 

Attachments

  • logRules.PNG
    logRules.PNG
    7.1 KB · Views: 178
Last edited:
Physics news on Phys.org
  • #2
##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.
 
  • Like
Likes FritoTaco

FAQ: Big O/Little O, Big Ω, little ω

1. What is the difference between Big O and Little O notation?

Big O notation represents the upper bound of a function's growth rate, while Little O notation represents the strict upper bound. In other words, Big O notation gives an idea of the worst-case scenario, while Little O notation gives a more precise estimate of the growth rate.

2. What does the "Big" and "Little" refer to in these notations?

The "Big" and "Little" refer to the "order of magnitude" of the function's growth rate. Big O is used for functions with a larger order of magnitude, while Little O is used for functions with a smaller order of magnitude.

3. How is Big Ω (Omega) notation different from Big O notation?

While Big O represents the upper bound of a function's growth rate, Big Ω represents the lower bound. In other words, Big Ω gives an idea of the best-case scenario for a function's growth rate.

4. What is the significance of using "Big" and "Little" in these notations?

The use of "Big" and "Little" in these notations is important as it helps in comparing the growth rate of different functions. It allows us to categorize functions based on their order of magnitude and understand how they will behave as the input size increases.

5. Can Big O/Little O and Big Ω/little ω be used for all types of functions?

Yes, Big O/Little O and Big Ω/little ω can be used for all types of functions, including polynomial, exponential, logarithmic, and more. These notations are commonly used in the analysis of algorithms and help in understanding the efficiency and scalability of a given algorithm.

Similar threads

Replies
4
Views
2K
Replies
2
Views
1K
Replies
2
Views
1K
Replies
7
Views
1K
Replies
1
Views
4K
Back
Top