2. The Mathematics of Algorithms

Question 1

How does the size and encoding of a problem instance affect algorithmic performance?

Answer 1

In most problems, the execution time of a program increases with the size of the data set. At the same time, overly compact representations may unnecessarily slow down the execution of the program. The encoding of the problem instance should not be the determining factor in whether the algorithm can be implemented efficiently. Proper data structures should be selected to represent the problem in order to design an efficient algorithm.

Question 2

How do constants affect algorithmic performance?

Answer 2

Some constants are assumed, such as standard integers being represented as four-byte words in computer architecture, but generally only affect algorithmic performance as a multiplicative constant. Algorithm designers generally ignore constants because performance costs that differ by a multiplicative constant are asymptotically equivalent. However, they may be important to take into consideration when implementing an algorithm in production code.

Question 3

How is algorithmic efficiency classified?

Answer 3

Algorithmic efficiency is classified according to the rate of growth of its execution time as a function of the size of the input problem instance. This common abstraction, however, ignores numerous details of the computing platform, such as the CPU, programming language and compiler, operating system, and other processes that may be running.

Question 4

Mathematically, what is the average performance of Sequential Search?

Answer 4

Where n is the number of distinct elements in the list and E(n) is the average number of examined elements:

E(n) = 1/n*(sum of all i in n) = (n*(n+1))/2n = ½n + ½

Question 5

Why is Sequential Search considered to have a linear rate of growth?

Answer 5

Because the number of elements examined scales linearly with increases in the size of the problem instance. The average number of probes is c*n, where c = 0.5. A fundamental fact of performance analysis is that the constant c is unimportant in the long run, because the most important cost factor is the size of the problem instance, n. Hence, the constant multiplier is ignored during algorithmic analysis.

Question 6

Why should the rate of growth not be the only consideration when selecting an algorithm?

Answer 6

Because constants matter (evidenced by the use of more powerful computers) and the size of n is not always large.

Question 7

How can the performance of an algorithm be predicted?

Answer 7

Through a statistical process known as regression analysis. The “fitness” of a trend line to the actual data is based on a value between 0 and 1, known as the R² value. R² values near 1 indicate high fitness.

Question 8

What is an example of an algorithm that demonstrates multiple distinct behavioral patterns?

Answer 8

For example, the Quicksort algorithm by Bentley and McIlroy is optimized by varying the strategy for problem sizes 7 and less, between 8 and 39, and for 40 and higher.

Question 9

What are some examples of different problem instances that might affect sorting algorithm performance?

Answer 9

• The data could contain large runs of elements already in sorted order.
• The input could contain duplicate values.
• Regardless of the size of n, the elements could be drawn from a much smaller set and contain a large number of duplicate values.

Question 10

Why may no single optimal algorithm exist for a given problem?

Answer 10

The worst case, average case, and best case may differ for different problem instances.

Question 11

Why is it valuable to know the worst-case performance of an algorithm?

Answer 11

It explains the maximum execution time that could occur in practice. It is also often the easiest case to analyze.

Question 12

How is the average-case performance computed for an algorithm?

Answer 12

The probability of a problem instance occurring is multiplied by its runtime, and the average-case is taken to be the sum of all these weighted probabilities for the entire set of the problem instances.

Question 13

Why is it valuable to know the best-case performance for an algorithm?

Answer 13

Though it rarely occurs in practice, it can provide insight into the optimal circumstances for the algorithm.

Question 14

What are lower and upper bounds?

Answer 14

The lower bound for the execution time of an algorithm is classified as Ω(f(n)) and corresponds to the best-case scenario. The upper bound for the execution time is classified as O(f(n)) and corresponds to the worst-case scenario.

Question 15

What is a tight bound?

Answer 15

In complexity theory, another notation Θ(f(n)) combines the lower and upper bounds to identify an accurate “tight bound”, where the lower and upper bounds have the same time complexity. However, O(f(n)) is more widely, though informally, used.

Question 16

What are the different performance families?

Answer 16

In order of decreasing efficiency:

• Constant: O(1)
• Logarithmic: O(log n)
• Sublinear: O(n^d) for d < 1
• Linear: O(n)
• Linearithmic: O(n log n)
• Quadratic: O(n²)
• Exponential: O(2ⁿ)

Question 17

What is an example of constant behavior?

Answer 17

Some primitive operations, such as comparing whether two numbers of the same word size have the same value. Performance differs on increase in word size, but all values of the same word size are computed with the same performance.

Question 18

How is the Guessing algorithm an example of log n behavior?

Answer 18

The potential range for the value that is sought is cut in half on each iteration, where the maximum number of guesses is calculated at 1 + floor(log(n)). With a range this formula becomes 1 + floor(log(high-low + 1)). At each iteration i, the algorithm computes a guess that is known to be within ±∈ = 2^k–1 – 1 from the actual hidden number, where ∈ is considered the error, or uncertainty, and is halved with each iteration.

Question 19

How is the Bisection algorithm an example of log n behavior?

Answer 19

The Bisection algorithm computes the input value for a continuous function where the output value crosses over a certain threshold by starting with the start and end points for a given range.

Question 20

What is an example of sublinear behavior?

Answer 20

A k-d tree in multiple dimensions can partition a set of n d-dimensional points efficiently. If the tree is balanced, the search time for range queries that conform to the axes of the points is O(n^1–1/d). For two-dimensional queries, the resulting performance is O(sqrt(n)).

Question 21

What is an example of linear performance?

Answer 21

The elementary addition procedure. There are multiple ways to implement this algorithm, and though they differ in their multiplicative constant, they are all linear. A lower bound can also be established on the algorithm of O(n).

Question 22

What is an example of linearithmic performance?

Answer 22

Divide and Conquer algorithms, which employ a recursive approach to solving subsets of the problem instance. The time complexity can be represented as t(n) = 2*t(n/2)+c*n, where the first and operand is the cost of the two subproblems and the second is the constant time to merge the results. The subproblem time complexity is calculated as t(n) = (2^k)*t(n/2^k)+k*c*n, and ends when 2^k = n (i.e. when k = log(n)). In the final base case when the problem size is 1, the performance t(1) is a constant d. Thus, the closed-form formula for t(n) = n*d+c*n*log(n), which can be simply written as O(n log n).

Question 23

What is an example of quadratic performance?

Answer 23

The elementary multiplication procedure. Like addition, there are multiple ways to implement the quadratic multiplication algorithm that differ in their multiplicative constants. However, there exist much more efficient multiplication algorithms that are significantly faster than the quadratic.

Question 24

What are some less obvious time complexities of algorithms?

Answer 24

The performance of many algorithms can be easily determined by reading the code or a description of the algorithm, for example nested loops indicating a quadratic algorithm. Others, such as Euclid’s GCD are less-obvious because it is not clear how many iterations will be performed for a given problem instance. In this case, too, there are multiple implementations that run in quadratic time with different multiplicative constant values.

Question 25

What is an example of exponential performance?

Answer 25

Solving a combination lock, where, for example, a lock with three dials requires 10³ (or 1000) attempts to brute force all combinations. Often, the exponential base is 2 rather than 10, but this performance holds true for any other base > 1. Exponential algorithms are only practical for very small values of n, however some algorithms with an exponential worst-case are still heavily used in practice because of their average-case behavior, such as the Simplex algorithm for solving linear programming problems.

Question 26

What are some characteristics of asymptotic growth?

Answer 26

An algorithm with better asymptotic growth will eventually execute faster than one with worse asymptotic growth, regardless of the actual constants. The actual breakpoint will differ based on the actual constants, but it exists and can be empirically evaluated. In addition, during asymptotic analysis it is only necessary to consider the fastest-growing term of the function.

Question 27

What is an example of why it is important to benchmark algorithmic performance?

Answer 27

Python’s exponentiation operator performs much more efficiently than other languages, however, it appears to exhibit different behaviors for different values. This is explained by Python implementing the Exponentiation by Squaring algorithm, rather than computing 2^x using a loop, which would cause quadratic performance. Benchmarks may uncover “surprises”, or unexpected slowdowns in computations due to the underlying implementation.