BUD optimisation

This is one of the most known optimisation techniques, and it is an acronym for:

• 🍼 Bottlenecks
• 👷 Unnecessary Work
• 📚 Duplicated Work

This technique should be one of your first options after developing a brute force solution. Since it focuses on detecting ways in which we could improve the time (Runtime) of your algorithm.

🍼 Bottlenecks

This refers to one, or a few specific parts in the code that increase the total runtime of your algorithm. This happens in two ways:

1. If you have a multi-stage algorithm and one of the runtime's is greater than the others - a bottleneck will occur naturally. For example, if you have an algorithm that first orders the elements of an Array O(N log N) and then searches for an element within the O(N) array. You could focus on reducing the second step to something like O(Log N) or even O(1), but you would still have the problem that the first step of the algorithm is (N Log N). Therefore, this should be the focus of your optimization.
2. When you have a piece of work in which many operations repeat - for example a O(N) search - this could probably be optimized to O(Log N) or O(N).

Example

If you have a function that has two arguments, the first one an array that has only unique numbers. The second a number (K) that will be used to find the pairs of numbers that have that difference. For example Array {1, 7, 5, 9, 2, 12, 3} and K = {2}. There will be four pairs of numbers within the array with a difference of two: (1, 3), (3, 5), (5, 7), (7, 9).

A brute force algorithm would do something like having 2 loops to compare each element against the other elements of the array and increase a counter for each pair that has the difference we want. This is quite inefficient since we have a loop inside another loop O (N ˆ 2).

One way to optimize this time would be to first order the array O(N Log N) and then have a loop to make the O(N) comparisons. Even this time could be improved. Would there be some way to optimize time when we have an unordered array?

The answer is with a HashMap. Then we can iterate over the array seeing if the element is + K or - K. And this will have an estimated time of O(N).

😦 Unnecessary work

Many times after arriving at a solution by brute force, one question we could ask ourselves is, could we reformulate the solution? An example:

Question: Print all positive integers in this equation, A2 + B2 = C2 + D2 where A, B, C and D are integers between 1 and 1000.

Brute force solution: 4 loops - each inside the other. That would give us a runtime of O (N ^ 4)

n = 1000

for a from 1 to n {
  for b from 1 to n {
    for c from 1 to n {
      for d from 1 to n {
        if (a^2 + b^2 == c^2 + d^2)
          print a, b, c, d
      }
    }
  }
}

This could be improved if we rewrite the equation like this: a2 + b2 = c2 + d2 d = sqrt (a2 + b2 - c2)

n = 1000

for a from 1 to n {
  for b from 1 to n {
    for c from 1 to n {
      d = Math.sqrt(Math.pow(a^2 + b^2 - c^2))
      if (a^2 + b^2 == c^2 + d^2)
        print a, b, c, d
    }
  }
}

😟 Duplicate work

If we use the same problem, and a brute force solution equal to the previous one, we can realize that we have duplicate work which we could simply save in a HashMap.

// pseudo code
n = 1000
myMap[result][listOfPairs]

for c from 1 to n {
  for d from 1 to n {
    result = c^2 + d^2
    append (c,d) to myMap[result]
  }
}

forEach result in myMap {
  forEach pair1 in listOfPairs {
    forEach pair2 in listOfPairs {
      print (pair1, pair2)
    }
  }
}

Using the HashMap to save each result that we computed we could reduce the time to O (N ^ 2).