What are the time complexities of the following programs Jus

What are the time complexities of the following programs? Justify. Provide a detailed comparison of merge sort algorithm and quick sort algorithm. Are the following statements true or false? Quick sort has the worst case running time theta (n^2). Merge sort has the best case running time theta (n log n). Counting sort has better running time than quick sort under all conditions. Any comparisons sort algorithm requires ohm (n log n) comparisons in the worst case. Rank the following functions in order of growth. Fill in each box with a number 1, 2, 3, 4, 5 or 6. (1 indicates the smallest value, while 6 indicate the largest.)

Solution

1) The time complexity of linear search is theta(n)

2)The time complexxity of binary search in thet(log n)

note::Binary search is more efficient compared to linear search .

3)comparison of merge and quick sort

a)In both the sorting techniques we divide the array and sort on it differently

b)average time complexity of both sorting techniques is O(n*logn)

c)worst case time complexity of merge is o(nlogn) and quick sort is o(n²⁾

d)In quick sort pivot element is used and in merge sort it is not used

e)quick sort is more efficient comapred to merge

2)ranking the function from 1 to 6 where 1 is fastest and smallest and 6 is slowest and largest

1----100logn

2----4nlogn

3-----(n+4)(n-2)

4----n⁴+200

5------2ⁿ⁺¹

^6-------2²ⁿ