## Description

1) Solve the following recurrence relation and give Ɵ relation for each of them.

a) T(n)=27 T(n/3) +n2

b) T(n)=9 T(n/4) +n

c) T(n)=2 T(n/4) +√𝑛

d) T(n)=2 T(√𝑛) +1

e) T(n)=2T(n-2), T(0)=1, T(1)=1

f) T(n)=4T(n/2)+n, T(1)=1

g) T(n)= 2 T(∛𝑛)+1 , T(3)=1;

2)

How many lines (as a function of n) does the following program print? Write a recurrence

relation and solve it by backward substitution. You may assume that n is a power of 2.

function f(n)

if n <= 1: print_line(“**”) else: for i=1 to n f(n/2) end for 3) Let T(n) denote the worst case number of comparisons (A[0]>A[1]) made by the following

function for an input array of n numbers. Give a recurrence relation for T(n). Solve the

recurrence relation.

Algorithm Function_f (A[0..n-1])

//Input: Array A of n numbers

//Output: A is sorted in increasing order

if n=2 and A[0]>A[1], then swap(A[0],A[1])

if n>2 then {

Function_f (A[0..ceil(2n/3)]) .

Function_f (A[floor(n/3)..n])

Function_f (A[0..ceil(2n/3)])

}

4)

Implement the quick sort and insertion sort algorithms and count the number of swap

operations to compare these two algorithms. Analyze the average-case complexity of the

algorithms. Compare the operations count in your report file to decide which algorithm is

better and support your analysis by using the theoretical average-case analysis of your

algorithms.

5) What are the running times of each of these algorithms (in big-O notation), and which would

you choose?

a) An algorithm that divides the problem into 5 subproblems where the size of each

subproblem is one third of the original problem size, solves each subproblem recursively and

then combines the solutions to the subproblems in quadratic time.

b) An algorithm that divides the problem into 2 subproblems where the size of each

subproblem is half of the original problem size, solves each subproblem recursively and then

combines the solutions to the subproblems in O(n2

) time.

c) An algorithm that solves the problem by recursively solving the subproblem of size n-1 and

then combine the solutions in linear time.