Question

Data Structures, C++, SORT running time. Would help is small explanation is included.

Problem 1. Select the worst-case running time of each function. bool search (int x, int* A, int n) if (linear search(x, A, n)) return true; insertion_sort(A, n); return binary_search (x, A, n); bool search_n_sort (int* A, int n) for (int x = 1; x <= n; ++x) if (linear_search(x, A, n)) ae()og(n) n) return true; insertion_sort(A, n); return false; bool sort_n_search (int* A, int n) insertion_sort(A, n); for (int x = 1; x <= n; ++x) if (binary_search(x, A, n)) return true; return false; void very_sort (int* A, int n) for (int i θ; i < n; ++i) insertionsort (A, n);

Answer 1

Worst-case running time of insertionSort(A, n) = Θ(n²)

Worst-case running time of binary_Search(A, n) = Θ(log(n))

Worst-case running time of linear_search(A, n) = Θ(n)

a) Worst-case running time of search method will happen when the linear search method returns false. In that case, we go on and sort the array using insertion sort and then search x using binary search.

Hence, worst-case running time = O(n²) [for insertion sort] + O(log(n)) [for binary search]

= O(n²)

b) Worst-case running time of search_and_sort method will happen when the linear search method returns false for x ranging from 1 to n. In that case, we go on and sort the array using insertion sort.

Hence, worst-case running time = O(n²) [for linear search for x ranging from 1 to n] + O(n²) [for insertion sort] = O(n²)

c) Worst-case running time of sort_and_search method will happen when the binary search method returns false for x ranging from 1 to n.

Hence, worst-case running time = O(n²) [for insertion sort] + O(n log(n)) [for binary search for x ranging from 1 to n]

= O(n²) (Since n² >= nlogn for larger values of n)

d) Please note that the best running time complexity of insertion sort is O(n) when the array is already sorted.

In this case, for i=0, we run insertion sort to sort the array. For subsequent runs of insertion sort, it takes O(n) time since the array is already sorted.

Hence, the worse-case running time complexity = O(n²) [for first insertion sort] + (n-2) * O(n) [for subsequent insertion sorts] = O(n²)