Considering Algorithms

Jake Thakur

April 2022

Basis

An algorithm is a finite sequence of well-defined instructions, generally used to solve a

problem, process data, or perform a calculation. Algorithms are typically defined mathematically

in the sense that the given procedure will work for any valid arguments. While understanding

how to apply a specific algorithm by hand is certainly important, it is not always the most

practical; for example, what if we need to sort an array of several thousand elements to be in

ascending order? It is certainly possible to do by hand; however, the process is time and labor

consuming with a margin for error. Rather, an algorithm can be programmed on a computer to do

this task for us, saving the cost of work and time, while also enabling reusability.

When comparing the execution of a computer algorithm to get a desired result to the

process of doing it by hand, it is in most cases true that the algorithm will be more efficient and

have 100% accuracy. But what if we compare an algorithm to another algorithm?

Analysis and Efficiency

Before comparing multiple algorithms to each other, individual analysis must be done for

each algorithm; essentially, answering the question, “How well does the given algorithm

perform?”

The performance of an algorithm is determined by several factors: the correctness of the

output data, the reusability of the code, how well it can handle different data, the efficiency with

respect to execution and runtime (time complexity) and with respect to hardware and memory

allocation (space complexity), and its overall functionality, i.e., does the algorithm output the

expected data, and how much time and resource does it cost to work?

When we compare algorithms, it is assumed that they work properly, primarily leaving

the concern of efficiency to be compared. Big-O Notation, “A theoretical measure of the

execution of an algorithm, usually the time or memory needed, given the problem size n, which

is usually the number of items.” (Black, P.), is a mathematical tool that can be used to evaluate

the time complexity and the space complexity of an algorithm. This makes the comparison of the

overall efficiency of an algorithm a much easier process by looking into the Big-O for each

algorithm and seeing which is better. An algorithm with a “better” Big-O is more efficient; the

complexities (from best to worst) are O(1), O(log n), O(n), O(n log n), O(nk > 1), O([k > 1]n), and

O(n!), illustrated below (Nilsson, S.).

The time complexity can be measured by stepping through the lines of code paying close

attention to the areas where there are arrays and other data structures, mathematical operations,

conditional statements, loops, and function calls, then consider how long the worst case takes to

run, i.e., the maximum possible runtime. Then the complexity in Big-O notation can be denoted

by using the following hierarchy: O(1) < O(log n) < O(n) < O(n log n) < O(nk > 1) < O([k > 1]n) <

O(n!); namely, if the code contains a segment that is of a higher order complexity, then the entire

code is of the higher order complexity (Mejia, A.). How this affects the runtime is significant; if

an algorithm has a factorial time complexity, like the LaPlace Expansion for determinants of nxn

matrices, (stack overflow) then as n increases, the runtime also increases by a factor of n

factorial, which is extremely compromising; consider the difference of a 5x5 and a 6x6 matrix

using this algorithm, the factor of growth would be at least 720 times.

The space complexity of an algorithm is slightly more complicated to determine than the

time complexity, however it follows the same conventions. In order to do so, we must first know

the size in bytes of the datatypes being used in the language being programmed in, then by

analyzing the areas where arrays and other data structures, mathematical operations, conditional

statements, loops, and function calls are utilized, the complexity is given by stepping through

each operation and calculating the worst case (most expensive) size in bytes demanded for

memory allocation; for example, an array of integers in Java requires 4 * n bytes. There are three

conditions for memory allocation that affect the overall space complexity of an algorithm (study

tonight):

➢ Instruction Space: the amount of memory used to save the compiled version of

instructions.

➢ Environmental Stack: when an algorithm is called inside another algorithm, the current

variables are pushed onto the system stack where they wait for further execution.

➢ Data Space: the amount of space used by variables and constants.

Reconsidering the example of sorting an array of several thousand elements to be in

ascending order, we can now compare the order of efficiency of various sorting algorithms to

decide which one is more optimal.

Based on the above chart (Rowell, E.), it looks like some sorting algorithms greatly outperform

others, so what is the point in even considering implementing the outperformed ones? While

certain algorithms may perform better than others (especially for certain data structures and

datatypes), the space and time complexities aren’t the only factors that should be considered;

what about the cost of development, project requirements, and design?

Development Practices and Constraints

While the runtime of an algorithm is amongst one of the most important aspects, what

about the development time? The time it takes to develop and implement an algorithm can

increase significantly depending on the (conceptual and semantic) difficulty of the algorithm

itself. The cost of development consists of the time and effort needed to develop something;

namely, how difficult it is to do. This leads to a question when the decision between the

minimum viable product (MVP) and the optimal product must be made; which one should be

prioritized (product focus)? The answer is dependent on many factors, such as the project

expectation and release date. For example, if the project needs an algorithm suitable for

processing thousands of queries at a time from multiple users, then the optimal product may be

preferred over the MVP. However, if it is a lightweight project that is expected to release within

a week, it may be prudent to take the MVP approach over the optimal product, using the extra

time to focus on additional urgencies in the development process.

The project requirements themselves are another factor to be considered in the

development process, such as language barriers, structure (separation of concerns), and

modeling. Often, a project is to be developed exclusively in a certain language, for a certain

purpose, i.e., JavaScript for web development and C++ for game development. An algorithm

may perform differently in different programming languages, for instance the size (in bytes) of

certain datatypes may vary from language to language. Additionally, some algorithms may be

more difficult to implement in certain languages. For example, mergesort can be more

complicated to implement in Java than in Python, because in Java it is prudent to use an Abstract

Data Type (ADT) and a comparator (CompareTo) in order to ensure there are no type errors,

whereas Python would simply interpret the data types of the arguments and compare them

accordingly; essentially, doing so in Java can lead to extra refactoring (you need to implement an

ADT interface) which lengthens the development process and can overcomplicate the code just

to reduce the complexity of the algorithm marginally. Not only would this affect the code itself,

but it would also affect the existing models, documentation, and architecture of the software,

which can lead to the project becoming convoluted. However, if it is important to the project

(and not too late in the development process), then it may be prudent to implement the more

complicated algorithm early on, as this will lead to stronger and more reusable code.

What if the product has already been released, but it is of interest to try optimizing the

code even more? Is it worth potentially breaking the (legacy) code to try to make the project

perform better? Luckily, backups of the project can be stored on (GitHub) repos and external

drives, so the risk of a full loss of the project is unlikely; additionally, the released version still

exists for the public and can be reverse engineered. With that in mind, it depends on how much

code really depends on it; exactly how large will the refactoring be? If there are several

dependencies on the target code, then it might greatly improve the performance of the project;

conversely, it might greatly increase the number of hidden bugs that will appear due to the

dependencies (Dietrich, E.).

Ultimately, it is important to understand and consider not only the algorithms and code

being used, but also the project requirements and expectations. When making decisions

surrounding the optimization of algorithms and the refactoring of code, it comes down to the

priorities of the development team, the leniency of the stakeholders, and the expectations of the

consumers.

8 
 
Citations 
Black, P. “big-O notation.” in Dictionary of Algorithms and Data Structures [online], Paul E. 
Black, ed. 6 September 2019. Retrieved April 15, 2022, from 
https://www.nist.gov/dads/HTML/bigOnotation.html 
Nilsson, S. “Big O notation: Definition and examples.” YourBasic. Retrieved April 15, 2022, 
from https://yourbasic.org/algorithms/big-o-notation-explained/ 
Mejia, A. How to find time complexity of an algorithm? Retrieved April 15, 2022, from 
https://adrianmejia.com/how-to-find-time-complexity-of-an-algorithm-code-big-o-
notation/  
Laplace expansion complexity calculation (recursion). Stack Overflow. Retrieved April 15, 
2022, from https://stackoverflow.com/questions/16655968/laplace-expansion-complexity-
calculation-recursion 
Space complexity of algorithms. Studytonight.com. Retrieved April 15, 2022, from 
https://www.studytonight.com/data-structures/space-complexity-of-algorithms  
Rowell, E. Know thy complexities! Big-O Cheat Sheet. Retrieved April 15, 2022, from 
https://www.bigocheatsheet.com/ 
Minimum viable product vs the optimal product. Product Focus. Retrieved April 15, 2022, from 
https://www.productfocus.com/minimum-viable-product-vs-optimal-product/ 
Dietrich, E. How do you know when to touch legacy code? DaedTech. Retrieved April 15, 2022, 
from https://daedtech.com/know-touch-legacy-code/ 