1. Write an algorithm that returns the sum of first m elements of an array S....

 

Transcribed Image Text:

1. Write an algorithm that returns the sum of first m elements of an array S. 2. Write an algorithm that outputs the smallest and largest values in the array S which has m unique elements. 3. Write an algorithm that reverses the order of the array s[1], s[2],...,s[n]. 4. Given an array s[1], s[2],...,s[n] such that n >1 and s[i] ≤ s[i+1] for all i. Write an algorithm that insert an input value x into the array so that s[i] ≤ s[i+1] for all i. 5. Order the following functions according to their order of growth (from the lowest to the highest). n!, 5 lg(n+ 100)¹0, 22n, n¹ + 3n³ + 1, nlgn, 3n 6. Prove the following assertion: If f(n) = 0(g(n)), then g(n) = N(f(n)). 7. Prove that lg(nk + c) = 0(lgn) for every fixed k > 0 and c > 0. 8 (1) If f(n) = 2n² + 1, prove that f(n) = 0(n²). If f(n) = 2n+2, prove that f(n) = 0(2"). (ii) (iii) If f(n) = 3 lg n + 2, prove that f(n) = 0(lgn). 1. Write an algorithm that returns the sum of first m elements of an array S. 2. Write an algorithm that outputs the smallest and largest values in the array S which has m unique elements. 3. Write an algorithm that reverses the order of the array s[1], s[2],...,s[n]. 4. Given an array s[1], s[2],...,s[n] such that n >1 and s[i] ≤ s[i+1] for all i. Write an algorithm that insert an input value x into the array so that s[i] ≤ s[i+1] for all i. 5. Order the following functions according to their order of growth (from the lowest to the highest). n!, 5 lg(n+ 100)¹0, 22n, n¹ + 3n³ + 1, nlgn, 3n 6. Prove the following assertion: If f(n) = 0(g(n)), then g(n) = N(f(n)). 7. Prove that lg(nk + c) = 0(lgn) for every fixed k > 0 and c > 0. 8 (1) If f(n) = 2n² + 1, prove that f(n) = 0(n²). If f(n) = 2n+2, prove that f(n) = 0(2"). (ii) (iii) If f(n) = 3 lg n + 2, prove that f(n) = 0(lgn).

Answer rating: 100% (QA)

1 Pseu... View the full answer