Newbie To Newbie Talk: Applying Algorithmic Design and Data Structure Techniques

 

    It turns out there is what you can say a best method to selecting the best algorithm to apply to data within any program.  When I first started my Data Structures & Algorithms class, I was nervous and excited at the same time to learn about different algorithms and how to efficiently store and sort data using advanced data structures.  I learned that there are many different algorithms to both search and sort information stored in arrays.  Some websites, such as geeks for geeks site and some peer review sites such as Zoe Bai's site with some YouTube videos, have entire lists of different algorithms each with differing complexities, each designed for a specific use.

The Information Technology (IT) community describes algorithm efficiency using two different measures of complexity. Time complexity is a function relating to the number of actions (n) that will be performed on an array (a[]). There are many different kinds of actions that an algorithm can perform on an array of data. Time can mean the number of memory accesses performed, the number of comparisons between integers, the number of times nested loops are executed, or some other way to define an algorithm's actions. 

It is common for people to incorrectly associate wall clock time with the time complexity of an algorithm. I also believe that time is also predicated on how fast your computer is that you are using to write and execute the function. Space complexity is the second measure of complexity.  It refers to a function used to describe the amount of memory that an algorithm will consume during its execution.  The IT community often speaks of the extra memory needed, in addition to the total memory occupied by the inputs. Bytes can be used to describe the amount of memory occupied, but you can also use the length of an array, the number of fixed size features, etc.

When computer scientists start analyzing the complexities of different algorithms, they use equations in the Big O format. One example of a Big O equation is O(n^2). On the Geek for Geek's site it describes four general steps to complete to determine the efficiency of an algorithm:

1.       Figure out what the input is and what n represents. The number n is often the number of elements in an array, but it can also represent other things.

2.       Express the maximum number of operations the algorithm performs in terms of n.  In my example equation, the maximum number of operations that will be performed is n^2.

3.       Eliminate all excluding the highest order terms. For example, in the equations a^2 + 2a, the highest order of terms is a^2.

4.       Remove all the constant factors. For example, in the equation a^2+2a+3, the "3" is the constant factor.

When you apply the above steps to f(n) =a0 + a1.n + a2.n^2 + am.n^m, the Big O notation is O(n^m). The algorithm's complexity varies based on the number of arrays and the number of elements in each array. A Big O equation is used to describe the theoretical worst-case running time, but every algorithm has the possibility of completing on the first execution, O(1).  There are many other ways to describe the complexity of an algorithm such as logarithmic generally - O(logn), linear – O(n), superlinear – O(nlogn), plus many more depending on the algorithm.

Because of our need to sort and then search through so many different data sets, we will also have an infinite number of algorithms to apply to your data sets. I visualize an algorithm as the various conditions that influence many decisions we make in the real world; you don't realize, but you use algorithms every day when you decide to do something. My personal experiences in different situations would affect the conditions specified in the loops of an algorithm.  In a computer program, the algorithm will apply specific conditions to data to sort and search it. A programmer needs to understand precisely what the data is and how much there is before they can select the most efficient algorithm. A simple comparison between algorithms is demonstrated by the similarities and differences between a Merge sort algorithm and a Bubble sort.  Merge sort can be extremely fast, but because of how it operates on its inputs, the space complexity is high.  Whereas a Bubble Sort is exceptionally slow, but it also has a very low space requirement.  Selecting an algorithm is every bit as complex as the equations used to describe them. Any different factors will influence the selection and design of both a program's data structures and the algorithms used to operate on its inputs.

 

References:

Complexity Analysis. (n.d.). (2021) http://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html

Geeks for Geeks, Analysis of Algorithms | Big-O analysis. (6 Mar 21). Retrieved https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/

Lysecky, R., Vahid, F., Lysecky, S., & Givargis, T. (2015). Data structures essentials. https://zybooks.zyante.com/#/zybook/DataStructuresEssentialsR25/chapter/1/section/3

Shaffer, C. A. (2013). Data structures and algorithm analysis (Links to an external site.) (Edition 3.2).  http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf

Zeigler, J. (2004). Time, complexity, space complexity, and the O-notation (Links to an external site.).  http://www.leda-tutorial.org/en/official/ch02s02s03.html

Zoe Bai, (3 Apr 2019), Big O Notation – Time and Space Complexity, https://medium.com/@zoebai_70369/big-o-notation-time-and-space-complexity-305a1e301e35