Fill in the following in increasing order O(), O(), O(), O(). O(), O(), O() from

Question

Fill in the following in increasing order O(), O(), O(), O(). O(), O(), O() from the set O(n^3), O(2^n), O(n), O(n(g(n)), O((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

1- Increasing Order

O(1) < O(log n)< O(n)< O(n log (n)) < O(n2) < O(n3) < O(2n) .

2- Linear search runs in at worst linear time and makes atmost n comparisions where n is the length of the array. if each element is equally likely ti be searched then linear search has an average caase of n/2 comparisons but the average case can be affected if the search probabilities for each element vary.
So the average time complexity for successfull search using array will be O(N).
with lists also the complexity remains O(N).

3- Binary search runs in at average logarithmic time making O(log n) comparisions where n is the number of elements in the array. using list the average time complexity becomes O(n) where n is the height of the binary tree. to search a given element in a BST compare it with root if the element is present at root then root is returned else if key is greater than root recur for right subtree of root otherwise recur for left subtree of root.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.