Fill in the following in increasing order from the set O(n^3), O(2^n), O(n), O(n
ID: 3868716 • Letter: F
Question
Fill in the following in increasing order from the set O(n^3), O(2^n), O(n), O(n(g(n)), O(l g(n)), O(1), O(n^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 advantage of the list implementation. Name an advantage of the array implementation. 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 array implementation.Explanation / Answer
Increasing order of complexity
O(1), O(lg(n)), O(nlg(n)), O(n), O(n^2), O(2^n), O(n^3)
Linear Search:
Average time complexity (Arrays) : O(n) (Every element to be searched)
Average time complexity (List) : O(n) (Every element to be searched)
Advantage with arrays is that it is an indexed structure (random access is possible) and accessing individual elements is easy, where as in the case of list we have to traverse the whole list to access each and every element. But list provides us an easy way if the list grows or shriks which is not the case with arrays. Insertion and deletion will be easier in list as compared to arrays. But reaching the exact position of insertion or deletion is fast in Arrays as it aloows random access but in case of list we need to traverse to that place node by node.
3.Searching the element in a binary serach tree, we will be traversing through the height
of the tree.At each comparison we will be going next higher level or height will increase by 1. So at the most once we cover the complete height of the tree, we will either get the searched element or not. The height of a balanced binary tree with n nodes is log(n) and hence our worst case search complexity is O(log(n)).
In the case of the sorted array, at each step we can compare the searched element with the middle value of the list and if it is more than the middle value we can consider the second half( middle+1....n) and if it is less we can look into first half(i.e 1....middle-1). We will get the element in the worst case once the lists will be reduced to single element.
So the number of comparisons will be the number of step to reach from n to 1 with each step n will be reduced by half. So for a given n, the number of steps will be log(n). so the the oder of complexity is O(log(n)).
In binary searh tree insertions and deletions will be slightly complex than insertion and deletion in sorted array.But looking at the complexity of insertion and deletion, the BST will log(n) but a sorted array will have O(n).Also the worst case for completely unbalnced search tree will be O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.