Question

1. Look at the following pseudo code:

Binary_search(int a[], int size)

{

……….// binary search and return

}

Selection_Sort(int a[], int z)

{

…..// do the selection sort

}

main()

{

    Selection_Sort(array, size);

    Binary_Search(array, item);

}

Calculate the time complexity of this code and use O() notation.

Answer 1

Solution - Given the following pseudo code -

Binary_search(int a[], int size){
// binary search and return
}

Selection_Sort(int a[], int z){
// do the selection sort
}

main(){
Selection_Sort(array, size);
Binary_Search(array, item);
}

Let us assume that size of array be n i.e size = n

We know that the worst case time complexity of Selection sort is O(n²) and the worst case time complexity of Binary search is O(logn).

In main(), first selection_sort() is called to sort the array then binary_search() is called to search for the item in sorted array.

So, the overall complexity of this code is sum of both complexities

Over all complexity = O(n²) + O(logn)

The algorithm as a whole has a worst case running time of O(n²).