Skip to content

DA2. Choosing the Best Algorithm

Statement

Suppose you are choosing between the following three algorithms:

  • Algorithm A solves problems by dividing them into five sub-problems of half the size, recursively solving each sub-problem, and then combining the solutions in linear time.
  • Algorithm B solves problems of size n by recursively solving two sub-problems of size n-1 and then combining the solutions in constant time.
  • Algorithm C solves problems of size n by dividing them into nine sub-problems of size n/3, recursively solving each sub-problem, and then combining the solutions in O(n2) time.

What are the running times of each of these algorithms (in big-O notation), and which would you choose?

For your discussion post:

  • Explain in your own words why you chose a particular algorithm.
  • Include one or two examples to explain your thought process to show what is occurring and how the methodology works.
  • Demonstrate your understanding of the intricacies of the algorithm you chose.
  • Use APA citations and references for any sources used.

Answer

Introduction

Divide and conquer is a strategy for solving problems that involves dividing the problem into smaller sub-problems, solving the sub-problems recursively, and then combining the sub-solutions to create a solution to the main problem. Each of this steps affects the running time of a divide-and-conquer algorithm, and the combining step is particularly important, as an expensive combine may negate the benefits of the divide-and-conquer strategy (Leiserson, 2005).

To evaluate each of the problems we will be using the Master Theorem technique presented by Vazirani et al (n.d.) for solving recurrence relations of the form:

\[ T(n) = aT(n/b) + f(n) \\ T(n) = aT(n/b) + O(n^d) \\ \]

where:

  • a is the number of sub-problems in the recursion.
  • b is the factor by which the problem size is reduced in each sub-problem.
  • f(n) is the cost of the divide and combine steps, which we assume to be O(n^d).

Then the solution would be:

\[ T(n) = O(n^d) \text{ if } d > log_b a \text{ ---(1)} \\ T(n) = O(n^d \log n) \text{ if } d = log_b a \text{ ---(2)} \\ T(n) = O(n^{\log_b a}) \text{ if } d < log_b a \text{ ---(3)} \\ \]

Algorithm A

For Algorithm A, a = 5, b = 2, f(n) = O(n), and d = 1. Therefore, we have:

\[ T(n) = 5T(n/2) + O(n) \\ \]

By the Master Theorem:

\[ log_b a = log_2 5 \approx 2.32 \\ d = 1 \\ d < log_b a \\ \]

This falls under the third case of the Master Theorem; hence, the solution is T(n) = O(n^log_b a) = O(n^2.32), and the total running time of Algorithm A is O(n^2.32).

Algorithm B

For Algorithm B, a = 2, b = 1, f(n) = O(1), and d = 0. Therefore, we have:

\[ T(n) = 2T(n-1) + O(1) \\ \]

By the Master Theorem:

\[ log_b a = log_1 2 = \infin \\ d = 0 \\ d < log_b a \\ \]

This falls under the third case of the Master Theorem; hence, the solution is T(n) = O(n^log_b a) = O(n^∞) which is exponential time complexity.

Algorithm C

For Algorithm C, a = 9, b = 3, f(n) = O(n^2), d = 2. Therefore, we have:

\[ T(n) = 9T(n/3) + O(n^2) \\ \]

By the Master Theorem:

\[ log_b a = log_3 9 = 2 \\ d = 2 \\ d = log_b a \\ \]

This falls under the second case of the Master Theorem; hence, the solution is T(n) = O(n^d log n) = O(n^2 log n), and the total running time of Algorithm C is O(n^2 log n).

Conclusion

After doing the analysis, we can answer the questions. The running times of each of the algorithms are: A = O(n^2.32), B = O(n^∞), and C = O(n^2 log n). Algorithm B is out of the scope because it is exponentially slow. Between Algorithm A and Algorithm C, Algorithm C is a better choice as it will perform better for large input sizes (lower time complexity).

The table below shows the running time of each algorithm for different input sizes:

Input Size Algorithm A = O(n^2.32) Algorithm C = O(n^2 log n)
2^10 = 1024 O(9.635 * 10^6) O(3.156 * 10^6)
2^20 = 1048576 O(9.285 * 10^13) O(6.619 * 10^12)
2^30 = 1073741824 O(8.947 * 10^20) O(1.041 * 10^19)

Notice how Algorithm A did better on the smaller input size of 1024, but as input size grows larger, Algorithm C becomes the better choice.

References