Skip to content

DA1. Solving Recurrences

Statement

  1. In your own words describe both brute force algorithms and branch and bound algorithms and identify the differences between the two. As part of your description you must discuss the Asymptotic behavior of each and discuss why this is important and how this might factor into the decision to use either algorithm design.
  2. Complete the following exercises and post your answers to the discussion forum.
    • Exercise 1: Solve thr provided recurrence relations explaining how you arrived at your solution.
      • \(f(n) = n^6 + 3^n\)
      • \(f(n) = 2^n + 12\)
      • \(f(n) = 3^n + 2^n\)
      • \(f(n) = n^n + n\)
    • Exercise 2: For the following Θ complexities write down a tight and a non-tight O bound, and a tight and non-tight Ω bound of your choice, providing they exist.
      • \(\theta(1)\)
      • \(\theta(\sqrt(n))\)
      • \(\theta(n)\)
      • \(\theta(n^2)\)
      • \(\theta(n^3)\)

Answer

Brute Force vs Branch and Bound Algorithms

An algorithm is a finite sequence of step-by-step, discrete, unambiguous instructions for solving a problem. There are many design paradigms or techniques for designing algorithms that solve particular problem including brute force and branch and bound algorithms (Tiapala, n.d.). Depending on the characteristics of the problem, one technique may be more suitable than the other.

Brute force algorithms are straight forward usually starts from the problem definition and it arrives at the final optimal solution after evaluating all possible solutions without much creativity; hence, it is easy to implement and inefficient in resource usage (Tiapala, n.d.).

Branch and Bound: is another technique that performs breadth-first search on the solution space after sorting it in a tree according to the problem concepts. The breadth-first allows for gathering some information about the expected solution. Each subtree in the solution tree is a branch, and the algorithm allows for skipping (pruning) branches that are known to be s worse than the expected solution or dissatisfy the problem constraints (Violina, 2021).

Let’s compare the two approaches using the N-Queens problem as an example. The problem is to place N queens on an N x N chessboard such that no two queens attack each other. The brute force approach evaluates all possible placements of queens first, and then select the valid ones The branch and bound approach starts by placing the first queen, and then start adding queens one by one; if the queen is safe, move to the next one, otherwise keep changing the position of the current queen until it is safe. You can see a nice visualization of the two approaches https://docs.drools.org/5.3.0.Beta1/drools-planner-docs/html/ch06.html#d0e2032

In terms of asymptotic behavior, both approaches (in the N-Queens problem) have a time complexity of \(O(n!)\), but the branch and bound approach is more efficient in practice because it prunes the search space while the brute force approach evaluates even dead-end solutions.

Exercise 1

The Theta notation represents the average case scenario of an algorithm (tight bound). It gives the actual growth rate of the function we’re analyzing. We tend to consider the term with the highest growth rate as n gets larger and ignore the rest. The following identifies the growth rate of the provided recurrences:

  1. \(f(n) = n^6 + 3^n ∈ \theta(3^n)\) because \(3^n\) grows faster than \(n^6\) as n gets larger.
  2. \(f(n) = 2^n + 12 ∈ \theta(2^n)\) because \(2^n\) grows faster than 12 as n gets larger.
  3. \(f(n) = 3^n + 2^n ∈ \theta(3^n)\) because \(3^n\) grows faster than \(2^n\) as n gets larger.
  4. \(f(n) = n^n + n ∈ \theta(n^n)\) because \(n^n\) grows faster than n as n gets larger.

Exercise 2

Let’s explain the concepts:

  • Theta (\(\theta\)): The average case scenario of an algorithm.
  • Big O (\(O\)): The worst-case scenario of an algorithm.
  • Big Omega (\(Ω\)): The best-case scenario of an algorithm.
  • Tight O Bound: The maximum growth rate of the function, it can not be exceeded.
  • Non-Tight O Bound: A growth rate that is higher than the Tight O bound, but still holds.
  • Tight Ω Bound: The minimum growth rate of the function, it can not go faster than this.
  • Non-Tight Ω Bound: A growth rate that is lower than the Tight Ω bound, but still holds.
Θ Complexity Tight O Bound Non-Tight O Bound Tight Ω Bound Non-Tight Ω Bound
\(\theta(1)\) \(O(1)\) \(O(n)\) \(Ω(1)\) -
\(\theta(\sqrt(n))\) \(O(\sqrt(n))\) \(O(n)\) \(Ω(\sqrt(n))\) \(Ω(1)\)
\(\theta(n)\) \(O(n)\) \(O(n^2)\) \(Ω(n)\) \(Ω(1)\)
\(\theta(n^2)\) \(O(n^2)\) \(O(n^3)\) \(Ω(n^2)\) \(Ω(n)\)
\(\theta(n^3)\) \(O(n^3)\) \(O(n^4)\) \(Ω(n^3)\) \(Ω(n^2)\)
  • Note that there is no non-tight Ω bound for \(\theta(1)\) because there is no asymptotic growth rate lower than \(Ω(1)\).

References