Select the big-O complexity for each operation/algorithm Question 1 options: Arr
ID: 3718603 • Letter: S
Question
Select the big-O complexity for each operation/algorithm
Question 1 options:
Array access
B-tree insertion
Selection Sort
B-tree search
dequeue operation
Insertion Sort
Stack push operation
Array insertion
Heapsort
linked-list search
O(1)
O(log(n))
O(n)
O(n log(n))
O(n2)
O(n3)
O(n!)
Array access
B-tree insertion
Selection Sort
B-tree search
dequeue operation
Insertion Sort
Stack push operation
Array insertion
Heapsort
linked-list search
1.O(1)
2.O(log(n))
3.O(n)
4.O(n log(n))
5.O(n2)
6.O(n3)
7.O(n!)
Explanation / Answer
O(nlogn)
This all worst case complexities.
Array access require O(1) time because we can access any element randomly with its address.
B-tree insertion require O(logn) time.
Selection sort's one pass require O(n) time so,overall it takes O(n2) time
B-tree search require O(logn) because we need to search at each levels.
Dequeue operations using array require O(1) time because we need to preform deletion from front which can be accessed directly.
Insertion sort in worst case takes O(n2) time
Stack push operation using array takes O(1) time because we can insert only at top.since we know where to insert we can do it directly.
Array insertion require O(1) time due to random access nature of array.
Heapsort require O(logn) time for one element deletion from minheap.to have a sorted list,we need to perform n times deletion.therefore,O(nlogn) time is required.
Linked list search requires one for loop so,O(n).
Algorithms complexity Array access O(1) B-tree insertion O(logn) Selection sort O(n2) B-tree search O(logn) Dequeue operation O(1) Insertion sort O(n2) Stack push operation O(1) Array insertion O(1) HeapsortO(nlogn)
linked-list search O(n)Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.