Is the given function polynomially bounded?

shivani @shivani1234
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 @shubhammeshr
19 Aug 2017 12:32 am

what is the meaning of polynomially bounded???

Niket Gangwar @niket151194
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 {\displaystyle |f(x)|\leq \;M|g(x)|{\text{ for all }}x\geq x_{0}}.

Now just assume g(x) to be some polynomial function(a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0}, ) which tends to bound f(x).

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