Time and Space Complexity of Non-Linear Data Structures

Time Complexity

Time complexity can be understood as a concept that constitutes the quantification of time taken by an algorithm or code snippet to execute. The time complexity is also a measure of the efficiency, such that the lesser the time is taken by the algorithm, the more its efficiency will be. 

We will be discussing only the worst-case time complexity in this article.

Space Complexity

Space Complexity can be understood as the amount of memory space occupied by a code snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser the space it takes, the more efficient it is.

Now let’s discuss the complexities of some non-linear Data structures.

Binary Tree

A tree in which all the nodes do not have more than two children is called a Binary Tree.

For Example: 

For a binary tree consisting of N nodes:

Time Complexity

• The time complexity for accessing any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for searching any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for inserting any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for deleting any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Also see, Morris Traversal for Inorder, hash function in data structure.

Binary Search Trees:

The first word of ‘Binary Search Trees’, namely ‘Binary’, tells us that every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

Lets us see an example of a binary search tree.

For a binary search tree consisting of N nodes:

Time Complexity

• The time complexity for accessing any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for searching any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for inserting any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)
     
• The time complexity for deleting any specific node:
  • Average Complexity: O(log N)
  • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Read More - Time Complexity of Sorting Algorithms And Application of Graph in Data Structure

AVL Trees:

For an AVL tree consisting of N nodes:

Time Complexity

• The time complexity for accessing any specific node:
  • Average Complexity: O(logN)
  • Worst Complexity: O(log(N))
     
• The time complexity for searching any specific node:
  • Average Complexity: O(logN)
  • Worst Complexity: O(logN)
     
• The time complexity for inserting any specific node:
  • Average Complexity: O(logN)
  • Worst Complexity: O(logN)
     
• The time complexity for deleting any specific node:
  • Average Complexity: O(logN)
  • Worst Complexity: O(logN)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Heap

For a heap consisting of N nodes:

Time Complexity

• The time complexity for finding the minimum / maximum value node is
  • Average Complexity: O(1)
  • Worst Complexity: O(1)
     
• The time complexity for inserting a node is
  • Average Complexity: O(log N)
  • Worst Complexity: O(log N)
     
• The time complexity for deleting the minimum / maximum value node is
  • Average Complexity: O(log N)
  • Worst Complexity: O(log N)
     
• The time complexity for extracting the minimum / maximum value node is
  • Average Complexity: O(log N)
  • Worst Complexity: O(log N)
     
• The time complexity to search/delete any node is
  • Average Complexity: O(N)
  • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

HashMap

For a hash map consisting of N values:

Time Complexity

• The time complexity to insert a value is
  • Average Complexity: O(1)
  • Worst Complexity: O(1)
     
• The time complexity to delete a value is
  • Average Complexity: O(1)
  • Worst Complexity: O(1)
     
• The time complexity to resize the map is
  • Average Complexity: O(1)
  • Worst Complexity: O(1)
     
• The time complexity to hash a value is
  • Average Complexity: O(1)
  • Worst Complexity: O(1)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Trie

A trie is considered to be a data structure used to store strings, in a manner such that, strings that have common prefixes share an ancestor.  

Time Complexity And Space Complexity: 

The space complexity for the creation of the trie is O(alphabet_size * average key length * N).

For different operations in a Trie, the average and worst time complexities are the same. 

• Insertion: 

    For a string of length ‘N’ to be inserted in the trie:

• Time Complexity: O(N), since we need to perform ‘N’ iterations.
• Space Complexity: O(N), since ‘N’ new nodes will be added which will occupy space up to O(N).
   

• Deletion:

    For a string of length ‘N’ to be deleted from the trie:

• Time Complexity: O(N), since we will have to traverse down the whole tree to reach the leaf node to delete.
• Space Complexity: O(1), as no extra space would be used. 
   

• Searching:

    For a string of length ‘N’ to be searched from the trie:

• Time Complexity: O(N), since we will have to traverse down the length of the string, to trace it.
• Space Complexity: O(1), as no extra space would be used.

N-ary Tree

N-ary trees also known as generic trees are trees in which every node has many children, and the number of children may not be known in advance.

Time Complexity

The time complexity for different operations in an N-ary tree is as follows:

• Searching: 
  • Time Complexity: O(N), where N is the maximum(worst) number of iterations to find a value at the last iteration.
     
• Addition of new node: 
  • Time Complexity: O(N), as we have for statement and no nested loops.

Average time complexity:

Worst time complexity:

Must Read Algorithm Types

Also read - Data Structure MCQ

Frequently Asked Questions

What is a Data structure?

A data structure is a way of storing data and organizing it, so that it is easier to use the information stored efficiently, change, add more of it or delete any. In different programs, we use different data structures based on the requirements of the operations further.

What are non-linear data structures?

Linear Data Structures are those data structures in which data is stored sequentially, and each element is connected to the previous or next element so that they can be accessed in a single run. Some examples of linear data structures are arrays, stacks, queues, etc.

Among linear and non-linear data structures, which one is more memory efficient?

Non-linear data structures are more memory efficient than linear data structures but this efficiency increases the complexity of non-linear data structures.

What is time complexity?

Time complexity can be understood as a concept that constitutes the quantification of time taken by an algorithm or code snippet to execute. The time complexity is also a measure of the efficiency, such that the lesser the time is taken by the algorithm, the more its efficiency will be.

What is space complexity?

Space Complexity can be understood as the amount of memory space occupied by a code snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser the space it takes, the more efficient it is.

Conclusion

In the above article, we learned about the time and space complexity of Non-Linear Data Structures, which is a very important concept required in the preparation for all the DSA based interviews. 

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

 Keep practicing and growing.