2.1 Complexity analysis: Represent the time complexity of the following recursiv

Question

2.1 Complexity analysis: Represent the time complexity of the following recursive algorithm, T(n), as a recurrence equation:

    int pow_2( int n ){
      if ( n==1)
               return 2;
     if ( n > 1)
               return ( 2 * pow_2( n-1 ) );
    }  

2.2 Complexity analysis: analyze the time complexity of the Top-Down implementation of the MergeSort algorithm on the following wikipedia webpage:
            http://en.wikipedia.org/wiki/Merge_sort

For

assume (iEnd - iBegin + 1) is n (that's the size of A), this algorithm will take c1.n + c0 to finish. Please represent the time complexity of TopDownSplitMerge(A[], iBegin, iEnd, B[]) as a recurrence equation. You don't need to solve this equation.

Explanation / Answer

Hi, Please find my answer.

Please let me knwo in case of any issue.

2.1) Complexity analysis: Represent the time complexity of the following recursive algorithm, T(n), as a recurrence equation:

int pow_2( int n ){
if ( n==1)
return 2;
if ( n > 1)
return ( 2 * pow_2( n-1 ) );
}

Here Recursive relation:

T(n) = T(n-1) + C (constant)

So, T(n) = O(n)

2.2)

TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])

   T(n) = O(n + m) : Mergint of two sorted array

   m+n = sum of elements of A and B

TopDownSplitMerge(A[], iBegin, iEnd, B[])

    T(n) = 2T(n/2) + O(n)

        O(n) = to merger sorted array

    So, Solving using Master theorem:
        T(n) = O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.