Data Structures, Algorithms, And Big O Notation! A Beginners Guide.

You may or may not have heard the term “data structures and algorithms” before. If you are in the realm of computer science I’m betting you have. To someone unfamiliar these words sound technical and intimidating. In the world of software development crossing paths with this eventually is inevitable, and thinking and practicing in these terms I believe makes the difference between developing code that simply ‘works’ and developing code that is efficient. This article will define each term followed by a brief summary of ‘big O’ notation. Because this subject matter may or may not interest most of you, I have made the decision to use an old anime ‘Big O’ as a consistent reference point for example analogies.

I may or may not regret this decision, but I’m sticking to it.

Data Structures, what are they?

A data structure is a way of storing and organizing information (aka data) that allows it to be accessed and manipulated efficiently. Data structures are widely used throughout software engineering and computer science. Chances are if you are even just beginning your journey on learning to code, you’ve already worked with them a whole bunch. The scope and variety of all of the different data structures in regards to software development is vast, but here are two of the more common data structures:

• Array: data is organized within brackets in sequential order. Each data entry within these brackets is called an element and is separated by a comma. These elements can be accessed via numbered indexes which start at 0 and increment per data entry. A Javascript example would be:

below is an example of how to extract a value from this array

> catchPhrase[0]
"Big"

• Hash: data is organized within braces with a key pointing to a value. These key/value pairs are generally separated by a coma. The data (value) can be accessed by its key. This has the advantage of having a constant reference point to access said value. The syntax for this varies in different languages, and in Javascript this is called an object. Here’s a Javascript example:

below is an example of how to extract a value from this hash

> characters['Android']
"Dorothy"

A visual aid for different data structures, these can even be nested inside one another.

What is an Algorithm?

An algorithm is the procedure or process you use for solving a problem or performing a task. In the next section we will look at how algorithms have their efficiency classified using Big O notation. We can use an analogy for a common task as an example of an algorithm. The common task being building a gigantic crime fighting robot like in the show I’ve regrettably made the decision to continuously reference. Here are the theoretical steps:

1. Be a Bruce Wayne esq. billionaire.
2. Either go to giant robot building school or hire someone who has.
3. Buy required tools and materials.
4. Assemble Gundam Wing style robot or hire someone to do so.

For an example more closely related to computer programming I have chosen a Javascript function that finds the index in an array that matches a given element. If no element is found, false will be returned. Because this function is the ‘how’ of this task. The function IS the algorithm, and I will try to utilize both an array and a hash data structure in this example:

below are some examples of different returns this function might have, this function uses the previously defined catchPhrase array by default.

> findIndexOfElement("Showtime!")
2
> findIndexOfElement("Not Present")
false

This example was a bit complicated, but hopefully you get the idea and can follow along with the explanation given on each comment line denoted by //. Also this example does not take into account duplicate elements, and if such is the case this function will always return the last index of the duplicate element within the array.

A Brief Description Of Big O Notation

Sadly this has absolutely nothing to do with Big O Notation, but I’m stubbornly keeping this analogy.

In computer science Big O Notation is used to describe the execution time or memory required to execute an algorithm under the worst case scenario. Because many factors come into play when recording the time it takes to execute a particular algorithm, Big O Notation is NOT simply an average of benchmark runtimes recorded to execute an algorithm. It instead is a metric of how quickly the runtime grows in relation to the input to arrive at the desired conclusion.

The syntax of this notation is not very intuitive but I will do my best to explain. In big o notation “o” stands for the order of magnitude which is a reference to the class of scale of any numerical value in which each class contains values of a fixed ratio to the class preceding it. An example of this would be comparing the weight of a giant robot to the weight of a human. In which the weight of a giant robot can be described as many orders of magnitude larger than the weight of a human. The “n” in big o notation typically represents the size of the input such as an array containing a single element or an array containing thousands of elements. I really wanted to go with another anime reference here, but I thought I’d spare you just this once.

Here are some examples of big o notation (using Javascript as reference):

• Constant Time or O(1) the algorithm has a constant run time relative to its input. Generally this is something that can be done in one “step”

• Linear Time or O(n) the algorithms execution time increases relative to the size of its input. Generally this is some basic iteration

• Quadratic Time or O(n²) the algorithms execution time increases relative to the size of its input squared. Generally this involves looped iteration

As you can imagine the runtime for this increases exponentially as the input increases because you are iterating through the entire array per element.

Conclusion

The data structure you use and algorithm you design can vary greatly but do matter. Some data structures are better suited for organizing a particular set of data than others, and it’s important to start thinking in terms of big o notation when coming up with algorithms to solve problems. Doing so will not only benefit you as a software developer, but will also keep your code succinct and efficient.