Algorithms are specific sets of tasks a computer performs to solve a problem. An algorithm can be as simple as adding two numbers together, or as complex as calculating a rocket’s trajectory.
Be it complex or simple, one major factor that is always considered when choosing an algorithm to use for any operation is the efficiency. The efficiency of an algorithm is determined by how fast the algorithm can perform a given task.
When measuring how fast an algorithm is, we do not take real time into account. Rather, what is considered is the amount of “steps” that will be required by the algorithm to complete its task in a worst-case scenario.
The reason why this is done is due to the difference in the hardware capabilities of computers. Some computers are better than others in terms of speed and processing. What this means is that a computer X equipped with an 8GB RAM chip for example, might run an algorithm for 2 seconds, while another computer Y with lesser specifications might take 10 seconds to run the same algorithm.
This shows that measuring the speed of algorithms in real time will create a very big problem, because there would be no definitive way to determine how efficient an algorithm is.
In order to solve this problem, computer scientists created what is known as the Big O Notation.
The Big O notation is just the formalized way of expressing how efficient an algorithm is.
For reasons stated earlier, Big O notation focuses on the number of steps (a constant) an algorithm takes to complete its task rather than the time.
The Big O Notation helps establish the proportionality between the number of steps an algorithm requires and how much the data increases.
To understand the concept better, I’ll be explaining Big O notation using an unordered array (a data structure) and the four (4) basic operations that can be performed on it; Read, Insert, Search, and Delete.
Example of an unordered array
To start off, what is an array?
An array is simply a collection of similar elements. Each of these elements has its own unique index number with the first element having a starting index of 0.
Reading from an array requires just one step no matter the amount of data we have present in the array.
This is because the computer has the index of the required element that needs to be read, and all it needs to do is just go straight to the location where the element is stored and bring it.
This can be expressed in Big O notation as 0(1).
O(1) is used to represent the time complexity of an algorithm that will always need to take a constant amount of steps to carry out an operation.
So, an algorithm that always performs any given task in 10 steps can also be said to have a time complexity of O(1).
Algorithms with O(1) time complexities are generally considered to be more efficient than all other types of algorithm.
To search for a value in an array takes “N” number of steps. Where “N” is a variable that represents the number of elements that are present in that particular array.
What this means is that, in a worst-case scenario, the computer will have to search through every available data in the array one after the other, before it finds the element it is looking for.
This type of search is known as the Linear search.
Another example of a search algorithm is the Binary search. It is more efficient than the Linear search, but this algorithm can only be applied to an ordered array.
In Big O, Binary search is described as having a time complexity of O(Log N).
Even though the Binary search is more powerful than Linear search algorithm, it isn’t advisable to use it on ordered arrays of small sizes.
A Linear search algorithm is much suited for ordered arrays that are of less sizes.
Deleting a data from an unordered array will require the computer to perform “N” number of steps. Removing an element from an array will create an empty space in the array, and arrays don’t allow empty spaces.
To rectify this, the computer will have to adjust the remaining data elements by one step so as to fill up the empty space that was created by what just got deleted.
For example, if we were to delete an element from the beginning of an array containing 10 values, it would take the computer 1 step to delete the item, and 9 more steps to shift the remaining elements in order to eliminate the empty space.
In mathematical terms, it will take;
1 + (N – 1) = N steps.
(where “N” is the number of elements in the array, which in this case is equal to 10)
This means that the Big O notation for deleting from an unordered array can be represented as O(N).
Another operation that can be performed on an array is insertion. Just like the other operations, the number of steps required to insert a new piece of data in an array is dependent on where you want to put it, but we’re only considering the worst-case scenario to measure time complexities.
Using the same example of an unordered array of 10 elements. To insert a new element will require the computer to perform one step, but before inserting, the computer has to create a space for the new item by moving all existing elements by a step to the right.
In mathematical terms, this means that the computer will take:
1 + N = (N + 1) steps
In a worst-case scenario, inserting a new data into an array will require “N + 1” number of steps. Again, “N” is the number of elements that are in the array.
Algorithms are very important in programming and it is always advisable to try to determine how fast your code will run using a particular algorithm before implementing it.
I hope this post helped shed some light on how to determine the efficiency of algorithms using the Big O Notation.
If you have any questions, additions or corrections, do well to put them in the comment section. I’ll be glad to reply.
Thank you for reading.