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 c1(g(n)) <= f(n) <= c2(g(n))
then let g(n), c1, c2 = 1.
1<=1<=1
which is true for all n >= x0 for some x0 > 0.
Is this correct?
Re: Question on upperbounds of a function
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.
Re: Question on upperbounds of a function
I don't understand...
If the upper bound equals the lower bound, doesn't c1 have to equal c2?
Re: Question on upperbounds of a function
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.
Re: Question on upperbounds of a function
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?