Let us say there is a funtion 'f' and other function 'g',

Now 'f' will be said to be bounded by 'g' if,

f(x)=O(g(x)) and it can be written if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x_{0} such that .

Now just assume g(x) to be some polynomial function( ) which tends to bound f(x).

Maybe for example you can think of f(x)=sin(x) and g(x)= x.

^{[lg n]}that can be written as e^{lg(lg n)!}= e

^{lg n*}^{lg(lg n) }= (_{e}lg n )*lg(lg n) = n^{lg(lg n)}= O(n)which is polynomially lower bounded .

^{lg(lg lg n)!}= e^{(lg lg n)lg(lg lg n)}(e

^{lg elg n})^{lg(lg lg n)}= (lg n)^{(lg lg lg n)}^{lg lg n }= O(e^{n})^{(lg lg lg n) }can be written as O(e^{lg n}) = O(n)what is the meaning of polynomially bounded???

Let us say there is a funtion 'f' and other function 'g',

Now 'f' will be said to be bounded by 'g' if,

f(x)=O(g(x)) and it can be written if and only if there is a positive constant

Msuch that for all sufficiently large values ofx, the absolute value off(x) is at mostMmultiplied by the absolute value ofg(x). That is,f(x) =O(g(x)) if and only if there exists a positive real numberMand a real numberx_{0}such that .Now just assume g(x) to be some polynomial function( ) which tends to bound f(x).

Maybe for example you can think of f(x)=sin(x) and g(x)= x.