Big-O, Little-O, Big-Theta Question

  • Thread starter PAR
  • Start date
In summary, the conversation discusses finding functions f and g such that f belongs to O(g), but does not belong to \Theta(g) or o(g). One possible solution is to use oscillating or unpredictable functions, but a specific example is not provided.
  • #1
PAR
30
0

Homework Statement



Find functions f and g such that:

f belongs to O(g) AND f does not belong to [tex]\Theta[/tex](g) AND f does not belong to o(g).

Homework Equations


The Attempt at a Solution



Another way to phrase the question is replace the statement "f does not belong to [tex]\Theta[/tex](g)" with "f does not belong to [tex]\Omega[/tex](g)" simply by the definition of Big-Theta, and that f must belong to O(g). So the problem boils down to finding f such that it has an upperbound of g, but g is not so large that c*g (c is any constant) will always overtake f eventually, but g is not so small that it can be overtaken eventually by c*f where c is some constant.

I have tried logarithms, exponents and polynomials, but I can't find a solution. I also don't want to do a brute-force guess and check: guessing some f and some g. My only idea right now is to use some functions that oscillate, or act very strangely, but all of the examples I can think of don't fit the description of the problem, for example:

f(n) = 1 if n is odd and -1 if n is even

but I don't see how I can use that function in this problem.

Thanks.
 
Last edited:
Physics news on Phys.org
  • #2
Just figured it out, you can close this thread.
 

FAQ: Big-O, Little-O, Big-Theta Question

What is Big-O notation?

Big-O notation is a mathematical notation used to describe the limiting behavior of a function when the input size approaches infinity. It is commonly used in computer science to analyze the performance of algorithms.

What is the difference between Big-O, Little-O, and Big-Theta notation?

Big-O notation describes the upper bound of a function's growth rate, while little-o notation describes a tighter upper bound. Big-Theta notation describes both the upper and lower bounds of a function's growth rate.

Why is Big-O notation important?

Big-O notation allows us to analyze the time and space complexity of algorithms, which is crucial for understanding their efficiency and scalability. It also allows us to compare the performance of different algorithms and make informed decisions when designing and optimizing code.

How do you calculate the Big-O notation of an algorithm?

To calculate the Big-O notation of an algorithm, we look at the dominant term or terms in the algorithm's time or space complexity. We ignore any constants or lower order terms, as they become insignificant as the input size grows. The resulting expression represents the Big-O notation of the algorithm.

Can Big-O notation be used for all types of algorithms?

While Big-O notation is commonly used for time and space complexity analysis of algorithms, it may not be suitable for all types of algorithms. Some algorithms, such as randomized algorithms, may have a variable time complexity that cannot be accurately represented by a single Big-O notation.

Similar threads

Comp Sci Big O/Little O, Big Ω, little ω
Replies
1
Views
1K
Comp Sci Proofing Big-O Notation: O(max(f(n), g(n)))
Replies
4
Views
2K
Comp Sci Time Complexity Algorithm Proof
Replies
2
Views
1K
Question about wording of an algorithm-complexity problem
Replies
1
Views
2K
Is There Always a Theta Notation Between Big O and Omega?
Replies
1
Views
2K
Is Big-O Notation Symmetric for f(n) and g(n)?
Replies
7
Views
7K
Understanding Big Oh: Exploring the Best Function for a Given Equation
Replies
2
Views
2K
Big-O and Θ Questions Homework: Answers Explained
Replies
6
Views
5K
Language that cannot be decided by a TM using space O(log n)
Replies
1
Views
1K
Big O question: f(n) = n^(1.01) + n(log(n))^5, g(n) = n^(1.01)
Replies
24
Views
6K

Hot Threads

Recent Insights

Back
Top