To prove :

As this is a generic statement, it has to apply to every growth function. But all we know about the growth functions (in general) is their bound, in terms of

and

.

Also, we know that if

then

is an increasing function whose value is

. But, if

, then we can only say that

is non-decreasing and is bounded by

.

I guess my question is that how can we prove the generic statement above. Kindly shed some light on the proof strategy.

Thank you,

Vishwajeet.