Suppose, in question #1 \" 1. What is the asymptotic, worst-case running time us
ID: 641625 • Letter: S
Question
Suppose, in question #1
"1. What is the asymptotic, worst-case running time using big-O notation for searching for an value,
v, and determining if it is in the dynamic set (a Boolean result) if the dynamic set is stored:
a. In a sorted linked list?
b. In an unsorted linked list?
c. In a sorted array?
d. In an unsorted array?
e. A balanced (e.g., a red-black) binary search tree?",
the search procedure returned a linked list node that contained the
value or the index of the array that contained the value or a failure indicator (a NULL node or a
negative integer index). Clearly, this does not change the search time! Once the search is
complete, what is the asymptotic, worst-case running time using big-O notation for deleting the
value from the set if the dynamic set is stored:
a. In a sorted linked list?
b. In an unsorted linked list?
c. In a sorted array?
d. In an unsorted array?
e. A balanced (e.g., a red-black) binary search tree?
full answer please?
Explanation / Answer
1)
a. In a sorted linked list? O(n)----while searching it has to visit each node to node----
b. In an unsorted linked list?O(n)----while searching it has to visit each node to node----
c. In a sorted array? O(logn)---it is sorted so it can skip some elemnts while searching---
d. In an unsorted array?O(n)---it has to visit all ements----
e. A balanced (e.g., a red-black) binary search tree?O(logn)
2)
a. In a sorted linked list?O(1)-----in linked list deletion is one step process, Whether it sorted/unsorted is not a matter
b. In an unsorted linked list?O(1)
c. In a sorted array?O(n)-----it cant skip some elemnts it has to delete and shift back elements to fill deleted array place---
d. In an unsorted array?O(n)
e. A balanced (e.g., a red-black) binary search tree?O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.