The science of runtime analysis is also present in data structures, not only in
ID: 3930994 • Letter: T
Question
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.Explanation / Answer
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