a. Name two algorithms that solve the same problem with different time complexity. b. Determine the...

 

Transcribed Image Text:

a. Name two algorithms that solve the same problem with different time complexity. b. Determine the time complexitOf the following algorithm: (2 marks) Algorithm Ex3(A): Input: An array A storing n 1 integers. Output: The sum of the prefix sums in A. S 0 for i 0 ton-1 do S+s+A[0] for j 1 to i do S+S+A[j] return s c. Order the following functions by asymptotic growth rate: 4nlogn+2n 210 2logn 3n+100logn 4n 2n n+10n n nlogn Question 3: a) (2.5 Marks) Sort the following array of integers using the insertion sort algorithm: A=(85, 24, 63, 45, 17, 31, 96, 50). b) (2 Marks) Count the number of comparisons and swaps that you may need to complete the task in (a). ( ) T 07:02 ENG POLECAT a. Name two algorithms that solve the same problem with different time complexity. b. Determine the time complexitOf the following algorithm: (2 marks) Algorithm Ex3(A): Input: An array A storing n 1 integers. Output: The sum of the prefix sums in A. S 0 for i 0 ton-1 do S+s+A[0] for j 1 to i do S+S+A[j] return s c. Order the following functions by asymptotic growth rate: 4nlogn+2n 210 2logn 3n+100logn 4n 2n n+10n n nlogn Question 3: a) (2.5 Marks) Sort the following array of integers using the insertion sort algorithm: A=(85, 24, 63, 45, 17, 31, 96, 50). b) (2 Marks) Count the number of comparisons and swaps that you may need to complete the task in (a). ( ) T 07:02 ENG POLECAT