Asymptotic Analysis of Different Data Structures Operations

There are numerous data structures that come handy while problem solving. The main aim of these data structures is to help optimise brute force solutions. A very important step to master data structures is to know which ones are to be used in which cases.

To know when to use which data structure, the most important thing is understanding which kind of operations they help in optimising. Let’s try to explore the operations these different data structures provide optimal solutions for, by analysing the time complexities for the same.

Arrays are the simplest data structures but they can be used in very elegant problems.

  1. Accessing an element at a particular index: Accessing a particular element at an index is a simple O(1) operation. We can directly access arr[i] for getting the ith element in array arr.

Conclusion: Arrays should be used if we want to deal with indices and we need to quickly check or update values at particular indices.

Unordered/Hash Map
Unordered Maps or Hash Maps are simple data structures based on the concept of hashing. These can be imagined like a simple store of key-value pairs. Keys for hashmap could be anything — integers, strings or even complex classes/structures.

  1. Getting a value for a particular key: The main purpose of hash maps is to store certain values corresponding to some keys. The time complexity of getting the value for a key is O(1) in average. As hashing may lead to collisions, it might take O(n) in the worst case. Similarly updating the value for a particular key also takes similar time

Conclusion: Unordered Maps or HashMaps are helpful light weight data structures for maintaining frequencies or certain values corresponding to different keys.

Ordered/Tree Map
Ordered Maps or Tree Maps are similar to a Hashmap in functionality but different in internal implementations. Underlying idea behind this kind of map is a balanced Binary Search Tree.

  1. Getting value for a particular key: Getting a particular key in a balanced BST involves searching for it in the tree. This requires traversing the tree height which takes O(logN) time

Conclusion: Ordered Maps are similar to HashMaps in most of the features. It provides certain additional optimal operations like upper and lower bounds making it a very useful data structure for cases which require the keys to be sorted.

Stacks, queues and double ended queues are special linear data structures with rigid ideas of insertions and deletions.

  1. Insertion of element: Stack is based on Last In First Out Principle (LIFO). It can be visualised as a list where insertion means inserting at the end. Queues are opposite to stack and are based on FIFO (First in First Out). Insertion in Queue happens at the end too. Double Ended Queues are a hybrid version of stacks and queues where they allow insertion to happen both at the beginning and at the end. Operation of insertion in stacks/queues/dequeues is O(1) if done at the required positions. If we want to insert something at a random position, it will take O(n) time instead.

Conclusion: Stacks/Queues/Deques are very specific data structures that help in problems where we want to deal with insertions and deletions of either the last entered element or the one that entered first or in some cases, both. Ideally, a deque can be used to implement stacks or queues but memory wise, stacks and queues are more efficient.

Heaps/Priority Queues
Heaps and Priority Queues are data structures specifically aimed at finding smallest or largest elements quickly. They are especially helpful in problems dealing with greedy algorithms.

  1. Insertion/Deletion: Heaps are balanced binary trees thus making the height of the tree logN, if it has N elements. Inserting a new element in the heap or deleting an element from the heap will take O(logN) time. This will be followed by a heapify function generally to keep the structure of heap intact. Heapify will also take O(logN) time. Priority Queues are a little less extensible because of the fact that they allow only deletions of the root of the heap (which is generally the maximum or the minimum element).

Conclusions: Heaps are very beneficial in cases where we want to keep maintaining the maximum or minimum elements according to a particular criteria through certain insertion/deletion operations.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Programming Pathshala

We are working to democratise access to Tech Education. We help students learn coding and be confident about themselves.