Efficiency of Algorithms

Learn about the efficiency of algorithms in this lesson.


There’s a natural demand for a definition that says under which conditions an algorithm can be viewed as working efficiently. This classification is done due to the growth rates of the functions considered in the table given below.

Considering the classes of time complexity, we can say that the difference between the growth rates of polynomial and exponential functions is the most dramatic one. Sipser (2012) describes the characteristics of exponential time functions as algorithms that “typically arise when we solve problems by exhaustively searching through a space of solutions, called brute-force search.”

Table 1

Name Running Time Examples of Running Time
Constant time O(1)\mathcal{O}(1) 8
Log-logarithmic time O(loglogn)\mathcal{O}(\log \log n)
Logarithmic time O(logn)\mathcal{O}(\log n) logn,log(n2)\log n, \log \left(n^{2}\right)
Polylogarithmic time poly(logn)p o l y(\log n) (logn)2(\log n)^{2}
Linear time O(n)\mathcal{O}(n) nn
Quasilinear time O(nlogn)\mathcal{O}(n \log n)
Quadratic time O(n2)\mathcal{O}\left(n^{2}\right) n2,n2+2n+1n^{2}, n^{2}+2 n+1
Polynomial time poly(n)=2O(logn)p o l y(n)=2^{O(\log n)} n,nx,nlognn, n^{x}, n \log n
Exponential time 2O(n)2^{\mathcal{O}(n)} 2n,10n2^{n}, 10^{n}
Factorial time O(n!)\mathcal{O}(n !) n!n !

Table: Classes of time complexity with decreasing efficiency\text {Table: Classes of time complexity with decreasing efficiency}

Get hands-on with 1200+ tech skills courses.