1. Suppose the time complexity of an Algorithm A follows the recursion below: 2*T(n-1)+1 T(n) =...

  

Transcribed Image Text:

1. Suppose the time complexity of an Algorithm A follows the recursion below: 2*T(n-1)+1 T(n) = -{ } {} 1 n > 2 n≤2 Determine the Big-Theta notation of T(n). (20pts). (Statement (5pts). Prove (10pts), Conclusion (5pts)) 2. Compare the text's implementation of insertion sort with the following version. (10pts) Algorithm InsertSort2(A[0..n-1]) for i 1 ton - 1 do j-i-1 while j0 and A[j]>A[j+1] do swap(A[j]. A[j+1]) j-j-1 A. What is the time complexity of this algorithm? Explain the reason. (5pts) B. How is it compared to that of the version given in the Slides 6.1? Explain the difference and impact (time complexity). (5pts) 3.(10pts) Please read the Textbook Pg.153, Russian Peasant Multiplication, and answer the following questions. a. Write pseudocode for the Russian peasant multiplication algorithm. b. What is the time complexity class of Russian peasant multiplication? Why? 4. Find Peak Element (20pts) A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array "nums", find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -o. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time. Please provide your algorithm, necessary comments and time/space analysis. (Pseudocode will be fine). Example 1: Input: nums [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. Example 2: Input: nums [1,2,1,3,5,6,4] Output: 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6. -231 nums[i] <= 231 - 1 Constraints: 1 <=nums.length <= 1000, nums[i]=nums[i+1] for all valid i. 1. Suppose the time complexity of an Algorithm A follows the recursion below: 2*T(n-1)+1 T(n) = -{ } {} 1 n > 2 n≤2 Determine the Big-Theta notation of T(n). (20pts). (Statement (5pts). Prove (10pts), Conclusion (5pts)) 2. Compare the text's implementation of insertion sort with the following version. (10pts) Algorithm InsertSort2(A[0..n-1]) for i 1 ton - 1 do j-i-1 while j0 and A[j]>A[j+1] do swap(A[j]. A[j+1]) j-j-1 A. What is the time complexity of this algorithm? Explain the reason. (5pts) B. How is it compared to that of the version given in the Slides 6.1? Explain the difference and impact (time complexity). (5pts) 3.(10pts) Please read the Textbook Pg.153, Russian Peasant Multiplication, and answer the following questions. a. Write pseudocode for the Russian peasant multiplication algorithm. b. What is the time complexity class of Russian peasant multiplication? Why? 4. Find Peak Element (20pts) A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array "nums", find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -o. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time. Please provide your algorithm, necessary comments and time/space analysis. (Pseudocode will be fine). Example 1: Input: nums [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. Example 2: Input: nums [1,2,1,3,5,6,4] Output: 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6. -231 nums[i] <= 231 - 1 Constraints: 1 <=nums.length <= 1000, nums[i]=nums[i+1] for all valid i.

Answer rating: 100% (QA)

The given recursive function for the time complexity of an algorithm represented as Tn with the following recurrence relation Prove To determine the BigTheta Notation of Tn Upper Bound BigO We need to ... View the full answer