Time Complexity of Data Structures

Question 1

Dynamic Arrays

What is the time complexity for:

1. Adding
2. Removing
3. Replacing
4. Accessing
5. Traversing

Answer 1

1. Adding
   
   1. O(n) beginning
   2. O(1)+ end
2. Removing
   
   1. O(n) beginning
   2. O(1)+ end
3. Replacing
   
   1. O(1)
4. Accessing
   
   1. O(1)
5. Traversing
   
   1. O(n)

Question 2

Hash Maps

What is the time complexity for:

1. Adding
2. Removing
3. Replacing
4. Accessing
5. Traversing

Answer 2

1. Adding
   
   1. O(1)+ anywhere
2. Removing
   
   1. O(1)+ anywhere
3. Replacing
   
   1. O(1)+
4. Accessing
   
   1. O(1)+ by key
   2. O(n) by value
5. Traversing
   
   1. O(n)

Question 3

Singly Linked Lists

What is the Big O for:

1. Insert
2. Delete
3. Access

Answer 3

1. Inserting at the beginning = O(1)
   Inserting in between = O(n)
   Inserting at the end = O(1)
   Replacing in between = O(n)
   Replacing at the beginning or at the end = O(1)
2. Deleting at the beginning = O(1)
   Deleting in between = O(n)
   Deleting at the end = O(n)
3. Access at the beginning = O(1)
   Access in between = O(n)
   Access at the end = O(1)

Question 4

Stacks

What is the Big O for:

1. Insert
2. Delete
3. Access

Answer 4

1. Inserting = O(1)
2. Deleting = O(1)
3. Access in between = O(n)
   Access at the top = O(1)

Assumes Doubly Linked List implementation

Question 5

Queues

What is the Big O for:

1. Insert
2. Delete
3. Access

Answer 5

1. Inserting = O(1)
2. Deleting = O(1)
3. Access at the beginning = O(1)
   Access in between = O(n)

Assumes Doubly Linked List implementation

Question 6

Binary Search Tree

What is the Big O for:

1. Insertion
2. Deletion
3. Access
4. Traversal
5. Search

Answer 6

If balanced, O(log(n)) for all operations (except traversal)
If unbalanced, O(n) for all operations

Traversal = O(n)

Question 7

What are the 6 general data structure operations?

Answer 7

1. Insert
2. Delete
3. Access
4. Traverse
5. Search
6. Merge

Question 8

Strings

What is the time complexity for:
1. Adding
2. Removing
3. Accessing

Answer 8

1. O(n) beginning middle end
2. O(n) biginning middle end
3. O(1)