In: Computer Science
(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array of size n into k subsets each of size n/k and recursively searches only one of these k subsets. Which one of these k subsets should be searched is decided by making (k − 1) comparisons, each of which can be done in constant time. Clearly, the recurrence relation for this k-ary search algorithm can be written as,
T(n) = T(n/k) + (k − 1)
Since k is a variable in the above recurrence relation, as an algorithm designer, you have the flexibility to set the value of k. Suppose you set k = n 2/3 . Analyze running time of the resulting algorithm in Θ notation.
(b) Show that f(n) = 2n 2 + 5n+ 3 is O(n 2 ) by finding adequate constants c and n0 where f(n) ≤ cn2 for all n ≥ n0.
Dear Student
In generalized k-ary search algorithm if the size of partition is more than one the time complexity will be logrithmic but if you put k =1 or less than 1( Which is not practically possible) the algorithm becomes linear and looses the sub-linearity propoerty,