1. Connecting the dots — Big O and Array Data Structure
In my previous article, I mentioned that algorithms are steps performed on some data to solve some problem(s). Data structures are ways we structure, manage and organize data. For example, If you want to sort the videos in YouTube, we click the sort icon to sort. How does it sort? There are data structures available for sorting.
Types of Data Structures
Let us see the correlation of Big O and the Array data structure. Arrays are linear data structure were collection of items are stored contiguously in memory. Each item is identified using an index. The indexes of an array starts from zero. Arrays could be collection of strings, numbers or combination of both. We can add or remove items to an array. The efficiency of an algorithm changes based on the where you add or remove items in an array. You can insert or delete elements from the beginning, middle or at the end.
In the below diagram, there is an array of items listed where we are trying to add an item at the beginning. When we add an array, we unshift() the rest of the items and all the indices corresponding to the array needs reindexing. The same applies with removing an item [shift()]at the beginning of the array. Recollect what is Big O(n)? The time taken for this operation is proportional to the size of the array. So, it takes linear time to add or remove an element at the beginning.
To add an item in the middle of the array we use splice(). When we insert an item in the middle, the rest of the items needs reindexing. This is similar to adding array at the beginning of the array. Therefore, this operation will also be in linear time or Big O(n).
When we perform a push() or pop() items on an array at the end, we do not need to reindex. In this case, the time taken for this operation is constant to the size of the array. So, it takes Big O(1) or constant time to add or remove an element at the end. Easy?
Out put of the above code:
To summarize, Array will have time complexities of Big O(n) or Big O(1) depending on where insertion and deletion of items takes place and the space complexity will be Big O(n). In the next article, we will see another data structure with Big O notation.
If you like this article please follow and give me a clap!