Question

Task 1

1.1 - Mergesort has two major advantages over Quicksort. What are these advantages? Write at most 5-6 sentences.

1.2 - Mergesort complexity analysis, explain it via recurrence relation and its main strategy. Write at most 7-8 sentences.

1.3 - Why a recursive algorithm always needs a base case? 2-3 sentences at most.

1.4 - Write Fibonacci Sequence formula F(N) with its base cases. Just write the formula with base-cases.

1.5 - Show how F(N=4) is computed for Fibonacci Sequences recursively starting from its base cases. Write your base case and how each value is computed.

1.6 - What is the time complexity of computing recursive Fibonacci Sequence F(N). Give Big-O notation and explain your answer. 5-6 sentences at most.

Answer 1

1.1 The advantage of merge sort over quick sort ,

a. merge sort worst case time complexity is O(nlog(n)) where as quick sort worst case time complexity is O(n² ).

b. merge sort is stable where as quick sort is not stable, so it is very helpful in sorting for those arrays/list which maintain ordering througout of their computing.

1.2 the time complexity of merge sort is O(nlog(n)).it uses divide and conqure algorithm to perform sorting. its recurrence relation is T(n) = 2T(n/2) + O(n) , here 2T(n/2) is because at every time it divide the array into two half. and O(n) is because it always merge two half.

1.3 reccursive relation algorithm need a base case because recursive method call it self hence it may go in a infinite loop , so to break this infinite loop base case is needed, base case is a condition inside recursive method which causes recursive method to come out of infinite loop.

1.4 fibonacci sequence with a base case is T(n) = T(n-1) +O(1). , here base case is if(n<=1) return n.

so time complexity here is O(n).

1.5 fibonacci (n==4),

fib(n)

{

if(n<=1)

return n;

return fib(n-1)+fib(n-2)

}

1.6. the time complexity of fiboancci is O(n) it is because its recurrance relation is T(n) =T(n-1) +O(1) ,

thus upon calculating this recurrance relation its output is O(n).