Sorting in place in linear time and Ranking of functions by asymptotic growth

Question 1:
A. binary search is the most famous search algorithm. It is productive and furthermore one
of the most normally utilized methods for solving sorting problems. binary search works on an
already sorted information. It uses iteration to get what is being sort in a collection of elements
that are already sorted in a specific order.
i. Recurrence for a binary search when an array is passed as a pointer is r ( n)=r ( n
2 )+c
using master theorem to give solution of the above recurrence
x=1
y=2
f(n)=z
nlogyx =nlog21
=n0
=1
F(n)= Θ (nlogyx)= Θ (1) =z
Case 2 of theorem can work in the above recurrence
Therefore, soln is T(n)= Θ(log2n)
ii. When whole array is passed by copying instead of pointer to binary search function;
recurrence for binary search is given by;
Theta ( n )=Theta ( n
2 )+cN - where N is full list and n is current chunk
¿ Theta ( n
4 )+ 2 cN- the iteration during search is given by dividing value of n by
2 in every iteration. That’s multiply initial value of n by ½ ¼ to 1/8
¿ T ( 1
8 n )+2 cN
¿ ∑
i=0
l og 2 n−1
¿ ¿2ic( N
2i )
=cNlog2n
= Θ (nlog2n)
The answer therefore is T(n)= Θ(nlog2n)-

iii. When the array is passed by coping such that only the sub range of the size n can be
accessed by the binary search function
Recurrence for binary search when array in passed sub range is given by;
T ( n )=T (1
2 n )+ zN
Using master theorem
x=1
y=2
f(n)=zn=n
hence, nlogba =nlog21
=n0
f(n)= Ω (nlog2a+c) when €=1, then 1(n)≤zn, where z>1
theorem 3 of master theorem can be used on this recurrence, therefore final
equation for the big O notation will be Theta(n)= Θ(n).
A. Merge sort- as used in algorithm is a divide and conquer method. It makes the array into
two equal section. It starts by sorting the first and the sort the second half. It then merges
the two sorted arrays.
i. When an array is passed by a pointer to merge sort
Recurrence for merge sort when passed is given by.
r ( n ) =2r ( n
2 )+ zn
using the master theorem to get solution to the above problem we have for this
recurrence
x=2
y=2
f(n)=zn=n
thus
nlogba becomes
= nlog22
=n1
There theorem master two will be used in this recurrence
The answer to problem is given by T(n)= Θn(log2n)

ii. When the array is passed by copying instead of pointer, to merge sort function:
In merge sort, recurrence when array is passed by copying is given by;
T ( N )=2T ( n
2 )+ zN +2 N
¿ 4 T ( n
4 )+ zn+ 4 N +2 z ( n
4 )
¿ 8 T ( n
8 ) +2 zn+8 N +4 z( n
4 )
∑
i=0
l og n−1
¿ ¿n+2iN)
= ∑
i=0
l og n−1
❑zn+N ∑
i=0
l og n−1
❑2i
=zn lg n +N 2 lgn−1
2−1
=zn lg n+Nn-N
= Θ(Nn)
Θ(n2)
iii. When the series of elements (array) is passed by copying such
that only sub range of size n can be accessed by merge sort
method
Recurrence when array is passed by copying in merge sort
T(n)=2T( 1
2 n)+zn+2( 1
2 n)
=2T( 1
2 n)+zn+n
=2( 1
2 n)
=2T( 1
2 n)+n(z+1)
Using master theorem.
For this case of recurrence
x=2
y=2
f(n)=zn=n
thus
nlogyx becomes
= nlog22