1. Fill in the following in increasingorder O(1), O(log n), O(n), O(n log n), O(
ID: 3896079 • Letter: 1
Question
1. Fill in the following in increasingorder
O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n)
2. Linear search can be done on data in an array or in a list. What is the average time complexity for successful search using an array? Using a list? Name an advantageof the list implementation. Name an advantage of the arrayimplementation.
Linear search on an array is O(1) for a sorted list and O(n) for an unsorted list, while linear search on a list of O(n). Linear search is faster, but has to be presorted. The list can be any order.
3. Binary search can be done on data in a sorted array or in a binary search tree.What is the average time complexity for successful search using the array? Using the BST? What is the worst case time complexity for each? Name an advantage of the BST implementation. Name an advantage of the sorted arrayimplementation.
Explanation / Answer
1. This is the increasing order of time complexity,
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O( 2n).
2. If we do linear search on array, the average time complexity is O (n) . This is the case that the searching element may be somewhere in middle.
If we do linear search on Linked list, the average time complexity is same as array which is O (n) . This is the case that the searching element may be somewhere in middle.
Advantage of using Linked list over Array is :
Linked list can store elements in non-contiguous memory locations but array can store elements in contiguous memory locations only. linked list has teo part in a node data part and address part.
Advantage of using Array over Linked list is :
Array require less memory compared to linked list, because list have an address part also to store along with each data. Linked list supports only sequantial access of elements but array doesn't have such restriction, it support non-sequantial access of elements also. becuase this restriction binary search cannot do on linked list .
3. Binary search can be done on both sorted array and Binary search tree. its average time complexity is O(log n ) in both cases.
worst case time complexity of binary search on sorted array is same O(log n). in BST the worst case time complexity is O(n), because while searching a value it has to visit all node in worst case.
Advantage of the sorted array implementation :
Array is a linear data structure. search can be done faster here.
Advantage of the BST implementation :
BST is a non-linear data structure. it is space efficient.
*****************END**********PLS GIVE ME GOOD RATING*******************
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.