Limited access

Upgrade to access all content for this subject

When discussing the running time of an algorithm, the three general types of functions that represent asymptotic bounds on the running time are polynomial, logarithmic and exponential. For this problem, a polynomial function is a function of the form $f(x)={ a }_{ n }{ x }^{ n }+{ a }_{ n - 1 }{ x }^{ n - 1 }+...+{ a }_{ 1 }x+{ a }_{ 0 }$, where $n>0$ and ${ a }_{ n }>0$. A logarithmic function is of the form $f(x)=\log _{ b }{ x } $, where $b>1$. An exponential function is of the form $f(x)={ b }^{ x }$, where $b>1$.

Using big O notation, meaning that if $f(x)=O(g(x))$, then $f(x)\le c\times g(x)$ for all $x\ge { x }_{ 0 }$, where $c$ is a constant greater than zero, list the three types of functions in ascending order of their growth rate.

This means if $f(x)$ comes before $g(x)$ in the list, then $f(x)=O(g(x))$.


Polynomial, Logarithmic, Exponential


Logarithmic, Polynomial, Exponential


Polynomial, Exponential, Logarithmic


It depends upon the variables $({ a }_{ i },n,b)$ present in the functions

Select an assignment template