Algorithms & Data Structures

Free Version

Upgrade subject to access all content


Asymptotic Bounds of Running Times


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