?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Easy

Asymptotic Bounds of Running Times

ALGOR-QWDP63

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))$.

A

Polynomial, Logarithmic, Exponential

B

Logarithmic, Polynomial, Exponential

C

Polynomial, Exponential, Logarithmic

D

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