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

• PAR
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.
PAR

## Homework Statement

Find functions f and g such that:

f belongs to O(g) AND f does not belong to $$\Theta$$(g) AND f does not belong to o(g).

## The Attempt at a Solution

Another way to phrase the question is replace the statement "f does not belong to $$\Theta$$(g)" with "f does not belong to $$\Omega$$(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:
Just figured it out, you can close this thread.

## 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.

Replies
1
Views
1K
Replies
4
Views
2K
Replies
2
Views
1K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
7
Views
7K
Replies
2
Views
2K
Replies
6
Views
5K
Replies
1
Views
1K
Replies
24
Views
6K