Question

a) (25 points) Suppose that you are asked to analyze the performance. Algorithms operate on 1D array of size nor 2D a of the algorithms below, write down the Big O or order of grow terms of n. If the algorithm cannot be applied to the array, write 0(1), O(log n), O(n), O(n logn), 90), O(n"), O(n!). The will only be given for reasonable Big O answers. & algorithms for their array of size nx n. For each growth (worst case scenario) in dy, write NA. Select answers from Tirst answer is given. Full credit Algorithm Big O (order of growth) or NA 0(1) 1. Find the 5th element in an array of size n O(no) (2) CELE 2. Determine if a sorted array of size n has any duplicates 3. Determine if two unsorted arrays each of size n have any common elements 4. Binary search for a target value in an unsorted array o logn) (1) 5. Find the maximum element in a 2D array of size nxn 6. Check if a 2D array is symmetric. That is, a[i]6) - Gli] for all (1) (13) 7. Find all combinations of the n elements in an array of size n 8. Sort an array of size n using merge sort 9. In an array where all elements are distinct, find the second largest element 10. Merge two sorted arrays each of size n/2 into a single sorted array of size n oln) Low o(1)

please check my answers if it wrong answer me

Answer 1

Solution:

4) Binary search for a target value in an unsorted array : NA.(Binary searches require the arrays to be sorted)

5)Find the maximum element in a 2-D array of size n x n: O(n²). (It is equal to the complexity of a linear search in the 2-D array)

6)Check if a 2-D array is symmetric: O(nlogn). (The number of comparisons go on decreasing by 1 for every row)

7)Find all combinations of the n elements in an array of size n: O(n!). (Similar to finding all combinations of strings from a string)

8)Sort an array of size n using merge sort: O(nlogn). (The array is broken down into halves and each is sorted and then merged)

The rest are all correct!