Efficiency of Algorithms

Introduction

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	$\mathcal{O}(1)$	8
Log-logarithmic time	$\mathcal{O}(\log \log n)$
Logarithmic time	$\mathcal{O}(\log n)$	$\log n, \log \left(n^{2}\right)$
Polylogarithmic time	$p o l y(\log n)$	$(\log n)^{2}$
Linear time	$\mathcal{O}(n)$	$n$
Quasilinear time	$\mathcal{O}(n \log n)$
Quadratic time	$\mathcal{O}\left(n^{2}\right)$	$n^{2}, n^{2}+2 n+1$
Polynomial time	$p o l y(n)=2^{O(\log n)}$	$n, n^{x}, n \log n$
Exponential time	$2^{\mathcal{O}(n)}$	$2^{n}, 10^{n}$
Factorial time	$\mathcal{O}(n !)$	$n !$

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