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.
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:
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:
- Be a Bruce Wayne esq. billionaire.
- Either go to giant robot building school or hire someone who has.
- Buy required tools and materials.
- Assemble Gundam Wing style robot or hire someone to do so.
2> findIndexOfElement("Not Present")
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
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.
- 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
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.