If you follow any Youtuber, a phrase you'll hear consistently among them all is...

"... the algorithm..."

As scary and undefinable as the term seems, "an algorithm is just a function, transforms the input into the output(organized data structure)." source

"In most cases, there exists more than one algorithm capable of handling the task at hand." source

The source linked above uses an example of a library. If you are looking for a book at a library, instead of programming a function that goes through each book, the author asks what other ways might you find the book.

It recommends using "the most optimal solution [being] one that consumes minimal energy and takes little time to complete the task."

The article goes on to identify the properties of an algorithm, as listed below.

• Input- An algorithm must possess 0 or more well-defined inputs supplied externally to the algorithm.
• Output- An algorithm should have 1 or more well-defined outputs as desired.
• Correctness- Every step of the algorithm must generate the correct output.
• Definiteness-Algorithms should be clear and unambiguous, thus every step of the algorithm should be clear and well defined.
• Finiteness- The algorithm should have a finite number of steps that must be carried out to achieve the task at hand.

Because most applications are data-driven, they do the following things:

1. Accept data
2. Store data
3. Process data
4. Organize data

"Often, the need to handle complex data results in the creation of Abstract Data Types(ADT) which are designed to create a logical description of how data is viewed and the operations that can be carried out on them."

A top-rated posting on Stack Overflow defines Abstract Data Types thusly, "Abstract Data Type (ADT) is a data type, where only behavior is defined but not implemented. Opposite of ADT is Concrete Data Type (CDT), where it contains an implementation of ADT."

The poster offers a real-world example,

"These ADTs allow us to handle data more efficiently such that we worry about what the data represents and not how it is constructed." source This makes sense to me in light of the book example. All books have two covers on the outside and pages within, but not all books are on a specific topic or even have the same content layout.

"This process is known as Data Encapsulation. Examples of such data types include the Array, List, Map, Queue, Set, Stack, Table, Tree, and Vectors."

Data Encapsulation is a fancy way of saying hiding the data. In reference to data structures and algorithms, it's a way to work with the data without revealing what the data represents.

Algorithmic Efficiency

As mentioned before, a major factor to consider when dealing with algorithms is efficiency. This is tested in two stages, theoretical and practical.

• Theoretical, or Priori Analysis: at this stage, it is assumed that factors including processor speed are constant, having no effect on the implementation of the algorithm.

• Practical, or Posteriori Analysis: Here is where software developers test the algorithm out using the preferred programming language. While it's being tested on a computer, the time it takes to run and the memory consumed are observed.

"Priori analysis makes use of asymptotic notation. It is a standard way of expressing an algorithm in terms of its time and space complexity. This is due to the fact that these are characteristics that cannot be measured or compared directly. The most commonly used type is David Knuth’s Big O Notation."

"The Big O Notation, also known as the upper bound of an algorithm or worst case, tells us that a certain function will never exceed or take more than a specific time to execute irrespective of the value of the input(n). This is considered a very effective way to approach analysis as it is able to tell us how our algorithms will perform in the worse case, perhaps with very large input." source

The big O for the example below is O(1).

int sumTwoNumbers(int a, int b){
return a + b
}

It is O(1) because no matter what numbers we use to represent a and b, the operation is always going to be the same, one simple addition operation. "We call this constant time because our complexity is always constant." source

Some built-in JavaScript methods, including .pop(), .push(), and .length() are all constant. Accessing a value happens in constant time, for example, popping off the last number happens in constant time. Basically, the method implementation doesn't disturb other index positions in the array.

But with a nested loop, for example, for each iteration of the outer loop, we will iterate through the inner loop. Our big O complexity will be O(n²) because the size of the input will affect the complexity.

nested loop example

for (let i = 0; i <= 2; i++) {
  console.log("- First level loop");
  for (let j = 0; j <=3; j++){
    console.log("--Second level loop");
  }
}

Some examples of built-in methods that use linear time are Shift and Unshift. They are both linear. The .shift() method removes the first array element and "shifts" all other elements to a lower index, starting from the [0] position. It affects the position of all elements in the array. What was [0], is shifted off, and what was [1], "Pamela" in the example below, becomes the new [0].

.shift() method example

let names = ["Keisha", "Pamela", "Angela", "Renee"];
names.shift();
console.log(names);
// outputs [ 'Pamela', 'Angela', 'Renee' ]

The same idea of linear complexity applies when restructuring the data using the built-in unshift() method

Unshift is linear because, from the [0] position, it adds a new array element pushing the other arr element over one space, .. it affects the position of all elements in the array, making it less constant and more complex.

The unshift() method removes the last array element and "shifts" all other elements to a lower index.

I lost some of my class notes in a tragic cut and paste accident but something that stood out to me in class was that there are design patterns for popular algorithms. Another way of looking at complexity is by looking at the number of operations performed. If we are trying to find a number out of a hundred, we'll find it easier if we cut the array in half, check to see if the number is in the first half, if it's not there, check the second half, and repeat. The chances of finding the number more efficiently are increased.

This is my first blog post/study guide for algorithms. Algorithms are starting to seem a little less mysterious.... for now, 😬😅...

Catch you in the next one. Thanks for reading! Let me know if this post was helpful. If you have any questions, feel free to leave a comment. You can contact me on Twitter @Asia Lakay.

References & Links

• Twitch.tv | Learn with Leon
• Scotch.io | A Gentle Introduction to Algorithms and Data Structures
• StackOverflow.com | What is ADT? (Abstract Data Type)
• TowardsDataScience.com | Big O
• Medium.com | Analyzing Performance of Arrays and Objects with Big O Notation