##### Is the given function polynomially bounded?

shivani
18 Aug 2017 05:35 pm
• [lg n]! can be written as [lg n][lg n] that can be written as elg(lg n)!

= elg n*lg(lg n) =  (elg n )*lg(lg n)​ = nlg(lg n) = O(n)
which is polynomially lower bounded .

• (lg lg n)! can be written as elg(lg lg n)! = e(lg lg n)lg(lg lg n)
(elg elg n)lg(lg lg n) = (lg n)(lg lg lg n)
• Note : nlg lg n  = O(en)
• So,  (lg n)(lg lg lg n) can be written as O(elg n) = O(n)
• Hence, (lg lg n)! is polynomically upper bounded.
Shubh
19 Aug 2017 12:32 am

what is the meaning of polynomially bounded???

Niket Gangwar
19 Aug 2017 04:25 am

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 x0 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.