Analysis of Algorithm Chapter 5

Which ones are the recurrence relation derived from Divide-and-Conquer Algorithm

T(n) = 6T(n/3) + n² ∊ ϴ(f(n)) , f(n) = ?

• n²

• log₃6

• n^1+log₃²

• n²logn

What is the best case of Quick sort

• well-ordered input

• reverse-ordered input

• choosing the pivot at the middle location

• the chosen pivot is the median

• choosing the pivot randomly

The constant time of Quick sort is on which process of Quick sort ?

• Pivot selection

• Find the position of pivot

• Bipartition of array

• Sorting the array

Which ones are true about analysis of time complexity of Quick sort in average case ?

• Given n elements of array, the probability of the pivot being to each position is 1/n

• Given the pivot is at the k^th location, the time of that case is T(n - k) + T(k - 1) + n

Given the time of the algorithm is aT(n/b) + n^d , what are the approach we can use to reduce the time of this algorithm ?

• reduce a when a < b^d

• reduce n^d when a > b^d

• reduce a when a > b^d

• reduce n^d when a < b^d

• n

• n²

• n^log3

• 3ⁿ

• n logn

Given X be 236, what is the value of a + b using the D&Q integer multiplication

which ones are true about applying Karatsuba algorithm on the multiplication of 48 and 2015

• After achieving the value Z0, Z1, Z2, the answer is

  Z2 x 10² + Z1 x 10 + Z0

• The multiplications for this process are 0x20, 48 x 15 and 48 x 35

• The multiplications for this process are 4x20, 8 x 15 and 12 x 35

• There are additional 4 recursions occur in this process