Thread: Question on upperbounds of a function

If g(n) is a upper bound of f(n), then g(n) is not a lower bound on f(n).

I think this statement above is false because if f(n) ∈ theta(1), which means the running time of f(n) is constant (ex. f(n) = 1), then this is a counter example of the above statement.
If c₁(g(n)) <= f(n) <= c₂(g(n))
then let g(n), c₁, c₂ = 1.
1<=1<=1
which is true for all n >= x₀ for some x₀ > 0.

Is this correct?

Hey Sneaky.

Can there exist a c2 such that c2 > 1?

Maybe you should outline what processes have the property where c1 and c2 both equal 1 and then say that the complement of processes of this set of processes don't follow that.

I don't understand...
If the upper bound equals the lower bound, doesn't c1 have to equal c2?

Yes that is true, but all I'm pointing out for you is to show what processes have this property and which ones don't so you can explain when its true and when its not.

So for example, if f(n) = n, which is a linear equation, then the upper bound can equal the lower bound right? But I don't understand if there is a function which the upper bound has to equal the lower bound at all times?