Answer the question with best run time complexity in terms of Big O notation 1)

Question

Answer the question with best run time complexity in terms of Big O notation 1) Given an array of *n* integer values that are stored in the ascending order, the problem is to insert a new integer value in the correct position so that the property of the ascending order is still preserved (basically the array stays sorted). 2) Same situation as above. The problem is to delete a given integer value in the array, if found. 3) Given a host string of size *n* and a pattern string of size *m*, the problem is to find if the pattern string is a substring of the host or not.For instance, let AAGCTCCCGTGGTTCC be the host string and CGT be the pattern string. In this example, CGT is a substring of the host whereas the pattern string TCCT is not. 4) Given a set of *n* integer values in an array, the problem is to find the minimum among all the integer values. 5). Given a set of *n* integer values in an array, the problem is to sort the array into descending order of values. 6). Given a set of *n* strings stored in an array, the problem is to find the lexicographically smallest one. You can assume that the size of any string is no greater than a fixed value *m*.

Explanation / Answer

1) O(log n)-By applying Binary search- First compare the number with middle element and go to the left or right side of the middle element based on wether the number is lesser or greater than middle element. 2) O(log n)- similar explanation as above. Do the same method as insertion of the number and delete if the number is already present at the location where it was supposed to be inserted. 3) O (n/m) in best case and O(n) in average case can be achieved using Boyer

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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