Here is a function max(i, n) that returns the largest element in positions i thr
ID: 638429 • Letter: H
Question
Here is a function max(i, n) that returns the largest element in positions i through i + n - 1 of an integer array A. You may assume for convenience that n is a power of 2.
function max (i, n: integer) : integer;
var
m1, m2: integer;
begin
if n = 1 then
return (A[i])
else begin
m1 := max(i, n div 2);
m2 := max(i+n div 2, n div 2);
if m1 < m2 then
return (m2)
else
return (m1)
end
end
a) Let T(n) be the worst case time taken by max with second argument n. That is, n is the number of elements of which the largest is found. Write an equation expressing T(n) in terms of T(j) for one or more values of j less than n and a constant or constants that represent the times taken by individual statements of the max program.
b) Give a tight big oh upper bound on T(n). Your answer should be equal to the big omega lower bound, and be as simple as possible.
Explanation / Answer
function max (i, n: integer) : integer;
var m1, m2: integer;
begin
if n = 1 then
return (A[i])
else begin
m1 := max(i, n div 2);
m2 := max(i+n div 2, n div 2);
if m1 < m2 then
return (m2)
else
return (m1)
end
end
The above procedure complete an example divides and conquers principle .It divides the problem into multiple sub problems of size n/2 two times .
T(n) = 2T(n/2) + 1
Apply the Master theorem on above condition
(a) T(n) = 2T(n/2) + 1
= 2{2T(n/4) + 1} +1
= 22.T(n/4) + 2 +1
...
= 2k.T(n/2k) + 2k-1 + … + 4 + 2 +1
Let us consider n = 2k
= 2k.T(1) + 2K -1 + … + 4 + 2 + 1
= 2K + 2K-1 + … + 4 + 2 +1
k
= 2i
i=0
= 2k+1 - 2
= 2(2K - 1)
= 2(n - 1)
= (n)
(b) Consider a = 2 , b =2, k =0
a>bk
T(n) = (nlogba)
= (nlog24)
= (n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.