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