1. What is the order of growth of the following operations for lists implemented
ID: 3599608 • Letter: 1
Question
1. What is the order of growth of the following operations for lists implemented with arrays?
add to the beginning of a list
[ Choose ] O(n) O(n^2) O(1)
add to the end of a list
[ Choose ] O(n) O(n^2) O(1)
delete from the beginning or middle of a list
[ Choose ] O(n) O(n^2) O(1)
delete from the end of a list
[ Choose ] O(n) O(n^2) O(1)
determine if the list contains an element
[ Choose ] O(n) O(n^2) O(1)
retrieve an element at a specific position
[ Choose ] O(n) O(n^2) O(1)
2.
What is the order of growth of the following operations for lists implemented with linked nodes with a head pointer only?
add to the beginning of a list
[ Choose ] O(1) O(n) O(n^2)
add to the end of a list
[ Choose ] O(1) O(n) O(n^2)
delete from the beginning of a list
[ Choose ] O(1) O(n) O(n^2)
delete from the end of a list
[ Choose ] O(1) O(n) O(n^2)
determine if the list contains an element
[ Choose ] O(1) O(n) O(n^2)
retrieve an element at a specific position
[ Choose ] O(1) O(n) O(n^2)
3.
What is the order of growth of the following operations for lists implemented with linked nodes with a head and a tail pointer?
add to the beginning of a list
[ Choose ] O(n) O(1) O(n^2)
add to the end of a list
[ Choose ] O(n) O(1) O(n^2)
delete from the beginning of a list
[ Choose ] O(n) O(1) O(n^2)
delete from the end of a list
[ Choose ] O(n) O(1) O(n^2)
determine if the list contains an element
[ Choose ] O(n) O(1) O(n^2)
retrieve an element at a specific position
[ Choose ] O(n) O(1) O(n^2)
Explanation / Answer
1)
add to the beginning of a list
O(1) - we can simply add an element to the start of the array.
add to the end of a list
O(1) - Directly accessible arr[n]
delete from the beginning or middle of a list
O(1) - Directly accessible arr[n]
delete from the end of a list
O(1) - Directly accessible arr[n]
determine if the list contains an element
O(n) - we need to scan all the array. so it will take o(n)
retrieve an element at a specific position
O(1) - Directly accessible arr[n]
2)
add to the beginning of a list
O(1) - Single linked list so can be done easily by changing pointer.
add to the end of a list
O(n) - We need to traverse to the end of the list. So it will take o(n)
delete from the beginning of a list
O(1) - head is known so can be done directly.
delete from the end of a list
O(n) - list need to be scanned.
determine if the list contains an element
O(n) - List need to be searched.
retrieve an element at a specific position
O(n) - We need to traverse to find the element.
3)
add to the beginning of a list
O(1) pointer to head is available.
add to the end of a list
O(1) pointer to tail is available.
delete from the beginning of a list
O(1) pointer to head available
delete from the end of a list
O(1) pointer to tail available.
determine if the list contains an element
O(n) access is required
retrieve an element at a specific position
O(n) access is required
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.