The science of runtime analysis is also present in data stru

The science of runtime analysis is also present in data structures, not only in algorithms. Adding an element to an Array List might be faster than adding an element to a LinkedList, because internally they function differently. Same goes for HashSet and TreeSet data structures. Your task is to fill in the table below with the runtime complexities of various methods from various data structures. Do a small research on it using any resource available to you and write a small description on why the complexity is like that.

Solution

Action

Complexity

Explanation

Adding an element in ArrayList

Amortized constant time

Its technically just an array

Adding element in HashSet

O(1)

Depends on initial capacity

Adding element in TreeSet

O(logn)

Iterative performance

Checking if LinkedList is empty

O(1)

As to check whether head node is present or not

Checking all nodes from LinkedList

O(n)

Depends upon number of nodes present

Checking if an ArrayList contains a given element

O(n) – Worst case

O(logn) – avg case

If we use Linear Search its worst case and avg case if we use Binary Search

Checking if an HashSet contains a given element

O(1)

As hash function takes its time complexity

Checking if an TreeSet contains a given element

O(logn)

Maximum height of a tree

Accessing the element of an ArrayList

O(n) – Worst case

O(logn) – avg case

Same as checking an item

Accessing the element of an LinkedList

O(n)

As we have to check all the elements

Adding the element at the beginning of an ArrayList

O(1)

As it takes small amount of time

Adding the element at the beginning of an LinkedList

O(1)

Just adding node to the head and making new node as head

Action	Complexity	Explanation
Adding an element in ArrayList	Amortized constant time	Its technically just an array
Adding element in HashSet	O(1)	Depends on initial capacity
Adding element in TreeSet	O(logn)	Iterative performance
Checking if LinkedList is empty	O(1)	As to check whether head node is present or not
Checking all nodes from LinkedList	O(n)	Depends upon number of nodes present
Checking if an ArrayList contains a given element	O(n) – Worst case O(logn) – avg case	If we use Linear Search its worst case and avg case if we use Binary Search
Checking if an HashSet contains a given element	O(1)	As hash function takes its time complexity
Checking if an TreeSet contains a given element	O(logn)	Maximum height of a tree
Accessing the element of an ArrayList	O(n) – Worst case O(logn) – avg case	Same as checking an item
Accessing the element of an LinkedList	O(n)	As we have to check all the elements
Adding the element at the beginning of an ArrayList	O(1)	As it takes small amount of time
Adding the element at the beginning of an LinkedList	O(1)	Just adding node to the head and making new node as head