Question

Group the following function by complexity category. $$\begin{aligned}&n \ln n \quad(\lg n)^{2} \quad 5 n^{2}+7 n \quad n^{5 / 2}\\\&n ! \quad 2^{n !} \quad 4^{n} \quad n^{n} \quad n^{n}+\ln n\\\&5^{\lg n} \lg (n !) \quad(\lg n) ! \quad \sqrt{n} \quad e^{n} \quad 8 n+12 \quad 10^{n}+n^{20}\end{aligned}$$

Short answer

The functions are categorized into complexity categories as follows: \(O(n^k)\): \(5n^2+7n\), \(O(\log n)\): \(\lg (n^2)\), \(O(n!)\): \(2^{n!}\), \(n!\), \(O(2^n)\): \(e^n\), \(n^n\), \(O(2^{2^n})\): \(n^n+ \ln n\), \(O(n \log n)\): \(n \ln n\), \(O(\sqrt{n})\): \(\sqrt{n}\), \(O(n)\): \(5^{\lg n}\), \(O(2^n)\): \(10^n+n^{20}\)

Step-by-step solution

Categorizing simple polynomial and logarithmic functions

These functions can be recognized by their mathematical format: \(5n^2+7n\) and \(\lg (n^2)\). These functions fall into polynomial time complexity (\(O(n^k)\)) and logarithmic time complexity (\(O(\log n)\)) respectively.

Categorizing more complex functions

Functions like \(2^{n!}\), \(n!\), \(n^n\), \(n^n+ \ln n\) are more complex. They are instances of factorial time complexity (\(O(n!)\)), exponential time complexity (\(O(2^n)\)), and doubly exponential time complexity (\(O(2^{2^n})\)).

Categorizing remaining functions

Functions like \(n \ln n\), \(\sqrt{n}\), \(5^{\lg n}\), \(e^n\), and \(10^n+n^{20}\), all have well-defined complexity categories. They belong to \(O(n \log n)\) (Linearithmic), \(O(\sqrt{n})\) (Square Root), \(O(n)\) (Linear), \(O(2^n)\) (Exponential), and \(O(n^{20})\) (Polynomial) time complexities respectively.

Key concepts

Polynomial Time Complexity

Polynomial time complexity is the category for algorithms where the time to complete the task raises to the power of a constant when the size of the input increases. It's frequently denoted by (O(n^k)), where n represents the size of the input and k is a constant. Examples of polynomial time complexities are linear functions like (5n), quadratic functions like (5n^2+7n), or even higher-order polynomials like (n^5/2) or (10^n+n^{20}). They are typically considered efficient for smaller values of n, but as n grows larger, these algorithms can become less practical.

Understand that polynomial algorithms are efficient and widely used for many practical applications, as they are relatively easy to analyze and implement. They make them ideal for problems where the input size won't grow extremely large, thus making the execution still manageable in reasonable time.

Logarithmic Time Complexity

Logarithmic time complexity is among the most desirable complexities for algorithms. It's symbolized as O(log n), showing that the execution time increases logarithmically with an increase in the input size. This means that when the input size doubles, the running time increases by a constant amount rather than doubling. Classic examples of logarithmic time complexity are found in binary search algorithms and operations on balanced binary trees.

For example, an algorithm that performs steps equivalent to repeatedly halving the problem size will have a logarithmic time complexity, such as (lg n)^2. Logarithmic algorithms are highly efficient, even for large data sets, because the number of operations grows much slower than the size of the input.

Factorial Time Complexity

Factorial time complexity describes algorithms that have a running time proportional to the factorial of the input size, noted as O(n!). These are some of the least efficient algorithms due to their very rapid growth rate. Essentially, for an input of size n, the algorithm performs n! operations, which is the product of all positive integers up to n. For instance, a function like (lg n)! suggests that the running time increases factorially with respect to the logarithm of the input size. Factorial time complexity usually appears with algorithms that solve problems by generating all possible permutations of their inputs, such as the brute-force solution to the traveling salesman problem.

Given its highly explosive growth with even small inputs, factorial complexity is often impractical and is avoided in algorithm design whenever possible.

Exponential Time Complexity

Exponential time complexity is another category representing algorithms with running times that grow exponentially based on the size of the input. This complexity is denoted as O(2^n), where for every additional element in the input, the computing time roughly doubles. Other bases for exponentiation such as O(4^n) are also considered exponential in nature. In such cases, even for relatively small values of n, the running time can become incredibly long. Algorithms dealing with computations like the powerset of a set or certain naive recursive algorithms (e.g., those for the Fibonacci sequence) may have exponential time complexities, like e^n or 2^n!.

Algorithms with exponential time complexity can quickly become unfeasible as they are only practical for very small data sets. When encountering such complexities, developers look for approximate or heuristic solutions to reduce computing times.

Linearithmic Time Complexity

Linearithmic time complexity, also known as quasilinear time, is a term used to describe algorithms whose time complexity is proportional to n log n. It is represented as O(n log n). These algorithms are faster than polynomial algorithms for large input sizes but slower than logarithmic algorithms. They often arise in algorithms that involve sorting operations, for example, quicksort and mergesort. An example of a function with linearithmic time complexity is n ln n, which grows more quickly than n but less quickly than the functions of polynomial time complexity.

Despite being more complex than logarithmic and linear algorithms, many linearithmic algorithms are very practical and commonly used due to their efficient handling of large data sets, provided the logarithmic component is not too large relative to n.