Question

4) Look at the following pseudo code: Binary..search(int a[], int size) { } wel binary search and return Selection Sort(int a[], int z) { ww/ do the selection sort } main { Selection Sort(array, size): Binary. Search(array, item): IS Calculate the time complexity of this code and use 0 ) notation. +12 fa 11.
c++

Answer 1

Here is the solution to your question. I tried my best to solve your doubt, however, if you find it is not as good as expected by you. Please do write your further doubts regarding this question in the comment section, I will try to resolve your doubts regarding the submitted solution as soon as possible.

If you think, the solution provided by me is helpful to you please do an upvote.

4) Look at the following pseudo code: Binary..search(int a[], int size) { } wel binary search and return Selection Sort(int a[], int z) { ww/ do the selection sort } main { Selection Sort(array, size): Binary. Search(array, item): IS Calculate the time complexity of this code and use 0 ) notation. +12 fa 11.

You have not provided any code or something else in the question, therefore I assume you know the algorithms well and you need only the total time complexity, in O() notation. Code contains 3 function Bibary_Search(): The time complexity of Binary_search() is Log(n), In Binary Search we divide the array into two parts and select a part based on sorted elements, and then divide the selected part into 2 parts and select one part, and so on. In other words we divide $N\rightarrow \frac{N}{2}\rightarrow \frac{N}{4}\rightarrow \frac{N}{8}\rightarrow \frac{N}{16}\rightarrow ....\rightarrow1$ . Mathematically, the number of terms of this sequence comes out to be, log N terms. So log(n) Selection_Sort(): it uses two loops and it's time complexity is N2, so n2 main(): it first call Selection_Sort() , (O(n2)) and then Binary_Search(), O(log(n)) , So total complexity in Big-Oh notation is max(n2 , log(n)) and answer is O(n2) So the time complexity of this code is O(n2).