Algorithm Development and Analysis

Algorithms organize information on the web, sort lists of items, and optimize routes on maps. Additionally, they help security engineers optimize data transmission and routing processes, reducing network latency and enhancing speed by efficiently managing the flow of information across the network. Put simply, algorithms help solve problems efficiently.

In this post, we will define an algorithm as:

Algorithm – a set of steps a program takes to finish a task.

This blog post explores the basics of algorithms, how they work, and why they are used.

🌸👋🏻 Join 10,000+ followers! Let’s take this to your inbox. You’ll receive occasional emails about whatever’s on my mind—offensive security, open source, academics, boats, software freedom, you get the idea.

General benefits and uses of algorithms

For those looking for a TLDR:

Efficiency – algorithms provide a systematic approach to problem-solving, ensuring that solutions are correct and efficient in terms of time and space.
Scalability – as the size of data and computational problems increases, algorithms help manage and process information effectively.
Optimization – algorithms are crucial for optimizing processes, from route planning in digital networks, GPS systems, and memory resource allocation.
Problem abstraction – algorithms allow engineers to abstract complex problems into manageable steps, making designing and implementing solutions easier.

Key characteristics of algorithms

Input – algorithms take input, which can be data, values, or variables, and process this input to produce an output.
Output – the result generated by the algorithm based on the given input.
Definiteness – algorithms are precise and unambiguous. Each step is clearly defined and capable of being executed.
Finiteness – algorithms must terminate after a finite number of steps, ensuring they do not run indefinitely.
Feasibility – algorithms must be practical and achievable within a reasonable amount of time and resources.

In less formal settings like interviews or this blog post, I simplify each algorithm to have a(n):

Problem statement
- A clear problem statement defines the task at hand.
Input
- An input, often a list of integers, is provided to the algorithm.
Output
- An output refers to a returned result.
  - An output can be nothing in cases of failure.
  - The algorithm should consistently return the same output for a given input.
Set of executable instructions
- Instructions should be executed in a specific order.
- Each step in the instructions must be explicitly clear and NOT require further subtasks.
Finite execution time
- An algorithm should complete within a finite amount of time.

Good algorithms – an evaluation

A good algorithm efficiently and accurately (aka “correctly”) solves a particular problem using well-defined and optimized steps.

Correctness

For an algorithm to be correct, it must produce the expected and desired output for all possible valid inputs while adhering to its specified requirements and constraints.

Correctness is proven through mathematical induction. It involves a specification (a base case) and a proof.

Proof example

Consider the following algorithm that calculates the sum of the first n positive integers:

Input – a positive integer n.
Output – the sum of the first n positive integers.

def sum_of_integers(n):

    return n * (n + 1) // 2

Now, let’s prove the correctness of this algorithm using mathematical induction.

Base case (n = 1)

The base case in mathematical induction is verified by directly confirming that the statement holds for the smallest possible value of the parameter or variable involved.

The algorithm calculates the sum of the smallest possible value of the variable involved. In this case, the smallest possible value is 1 (the first positive integer in the range), and the variable involved is n. When n = 1, the formula gives:

$\text{{sum\_of\_integers}}(1) = 1 \times (1 + 1) / 2 = 1$

So, the base case holds.

Inductive step

For the induction step to prove true, the proposition should hold for any arbitrary integer, k, AND it should hold for the next integer (k + 1) as well.

A. Assume that the algorithm is correct for some arbitrary positive integer $k$ , i.e., assume that:

$\text{{sum\_of\_integers}}(k) = \frac{k \times (k + 1)}{2}$

B. Now, prove the algorithm is correct for $k + 1$ , i.e., show:

$\text{{sum\_of\_integers}}(k + 1) = \frac{(k + 1) \times ((k + 1) + 1)}{2}$

C. Next, use the assumption and prove:

$\text{{sum\_of\_integers}}(k + 1) = \text{{sum\_of\_integers}}(k) + (k + 1)$

D. Substitute the assumption:

$= \frac{k \times (k + 1)}{2} + (k + 1)$

E. Combine the terms over a common denominator:

$= \frac{k \times (k + 1) + 2 \times (k + 1)}{2}$

F. Factor out $(k + 1)$ from the numerator:

$= \frac{(k + 1) \times (k + 2)}{2}$

So, the inductive step holds, ending the proof. It proves the algorithm is correct for all positive integers using mathematical induction.

Efficiency

Once correctness is established, the focus shifts to efficiency. Efficiency determines how quickly problems are solved, impacting user experience.

Imagine wanting to add a friend on a social media website who lives far away geographically (source). Next, think about how frustrating it would be if a social media platform asked you to wait a few hours to find that person because the search process is slow. That is why the efficiency (speed) of the search is essential.

Time and space complexity

Now, let’s see how we can analyze the usefulness of algorithms. Time and space complexity is how engineers measure algorithm efficiency.

Time complexity

A measure of how long it takes the algorithm to run.

Faster algorithms result in lower time complexity. Time complexity is illustrated by adding a friend on social media; quick searches enhance user experience.

Space complexity

Measures the amount of computer memory consumed by the algorithm.

Balancing time and space complexity is crucial for an algorithm’s utility.

In many cases, effective algorithms find a compromise between time and space complexity. If an algorithm is extremely fast but uses more memory than the computer has, it can overwhelm the system and fail to solve the problem.

A warning about universal optimization

Note that there is not just one way to determine if an algorithm is the best solution—it depends on the situation. In other words, the effectiveness of an algorithm varies based on the context or problem it is applied to. There is no universally optimal solution for all scenarios.

For example, consider a sorting algorithm: If you have a small dataset, a simple algorithm like bubble sort may suffice. Bubble sort is a straightforward and easy-to-understand sorting algorithm, making it suitable for small datasets where simplicity is more valuable than efficiency (source).

Bubble sort gif. Used on a post about algorithms. Source https://codepumpkin.com/bubble-sort/

However, for a large dataset, a more complex algorithm like merge sort or quicksort should be more efficient (source).

The “best” algorithm depends on the size and nature of the data you are dealing with.

Merge sort illustration used on a post about recursion and another post on algorithms. Source https://www.lavivienpost.net/merge-sort-using-divide-and-conquer/

Algorithmic strategies guessing game

Here is an example from a video course against the idea of one algorithm being universally optimal.

Consider a scenario where Olivia, John, and Jane are playing a guessing game. In this game, Olivia thinks of a number, and the other people try to guess it. After each guess, Olivia will give feedback to the guesser: “too low,” “too high,” or “correct!”

The winner has the fewest number of guesses. The overall goal is searching for a value.

We will explore how the choice of algorithm can be influenced by the range of possible numbers.

Scenario 1: small range (1-20)

Ceiling a number, $ceil(n)$ , refers to rounding it up to the nearest integer or whole number.

Olivia decides to think of a number between 1 and 20. John and Jane use different strategies to guess the number.

Linear search (sequential guessing)
1. John starts guessing from 1 and goes sequentially to 20. His guesses are 1, 2, 3, 4, and so on until he reaches 20.
2. He will find the target relatively quickly if the number is towards the beginning of the range.
Binary search (sorted range)
1. Jane guesses the midpoint of the range, which is .
  1. If Olivia’s chosen number is greater than 10, Jane knows the number must be in the second half of the range (11-20).
  2. If it is less than 10, the number must be in the first half (1-9).
2. Let’s say Olivia’s chosen number is 4, and she tells Jane that “10 is too high.” Based on the feedback, Jane narrows down the range. Jane now knows the number must be in the range 1-9.
3. Jane guesses the midpoint of the remaining range, which is $ceil(9 / 2) = 5$ . Based on feedback, Jane knows the number is less than 5. She narrows the range to 1-4.
4. Jane repeats the process, guessing the midpoint of the remaining range. She narrows it down until she finds the target.
  1. 1. Feedback: “Too low.”
    2. Now, the range consists of 3 and 4.
  2. 1. Feedback: “Correct!”

In this case, a linear search is most suitable because the range is small, and the simplicity of sequential guessing does not incur much overhead. To reach the target number, John takes 3 guesses while Jane takes 4.

Below, you can see a visual of how both searches compare when the target number is 9 (source).

Binary vs linear gif used on a post about algorithms. Source https://dizzycoding.com/binary-search-javascript-plus-big-o-performance-explained-simply/

Scenario 2: medium range (1-100)

This time, Olivia chooses a number between 1 and 100.

Linear search (sequential guessing)
1. John starts guessing from 1 and goes sequentially to 100. His guesses are 1, 2, 3, and so on until he reaches 100.
2. The number of guesses increases linearly with the size of the range, making this approach less efficient.
Binary search (sorted range)
1. Jane realizes that the range is larger, and using a linear search might take too many guesses.
2. Jane decides to use binary search by guessing the midpoint (50) and narrowing down the search space based on the feedback.

Let’s say Olivia’s target number is 75.

Here, John takes 75 guesses to reach 75, while Jane only takes 3:

1. Feedback: “Too low.”
1. Feedback: “Correct!”

In this scenario, the efficiency of binary search becomes more apparent as the range expands. The sorted nature of binary search becomes an advantage despite the additional step of maintaining a sorted list.

Scenario 3: large range (1-1000)

This time, Olivia selects a number between 1 and 1000.

Linear search (sequential guessing)
1. John dreads the thought of sequentially guessing from 1 to 1000. It would take a considerable number of guesses.
Binary search (sorted range)
1. Jane appreciates the efficiency of binary search even more in this case. The number of guesses is significantly reduced by repeatedly halving the search space.

In this scenario, the benefits of binary search become even more pronounced. The overhead of sorting the range is justified by the substantial reduction in the number of guesses needed.

These scenarios illustrate how the choice of algorithm depends on the size of the dataset, and different strategies become more or less advantageous based on the range of possible values.

Evaluating efficiency

To determine how efficient each algorithm is and which suits a given problem, consider the running time.

Running time

The running time is the number of tries or guesses in the worst-case scenario.
It indicates how long it takes the algorithm to run with a given set of values.

In the guessing game example, the running time represents the number of tries or guesses it takes for someone to guess the target number in the worst-case scenario.

Remember, no solution works for all problems, emphasizing the importance of establishing bounds (i.e., the size of the dataset) to choose the appropriate algorithm.

Conclusion

In conclusion, understanding algorithms involves comprehending their structure and evaluating their correctness and efficiency. As there is no one-size-fits-all solution, choosing the right algorithm requires considering the specific context and requirements of the problem at hand. So, whether you are implementing a linear search for simplicity or leveraging the efficiency of binary search, the key is to strike a balance between correctness and speed for optimal algorithmic performance.

If you enjoyed this blog post on algorithms, consider reading The Importance of Key Rotation.