Consider an method that operates on a list as follows: if the list has only one
ID: 3590396 • Letter: C
Question
Consider an method that operates on a list as follows: if the list has only one element, the answer is calculated directly for O(1) cost; otherwise the code traverses the list, and produces two new lists each containing half the original elements; then the method is called recursively on each sublist; the results of the recursive calls are combined with a constant amount of extra activity. Write the recurrence equation for the time cost T(n) when this method is run on a list of length n. What is the big-Oh for the function T(n)?
Explanation / Answer
We are partitioning the list in two halves and calling recursively
on those two halves. So by this we can write
T(n) = T(n/2) + T(n/2)
T(n) = 2 * T(n/2)
= 2 * 2 * T(n/4)
...
...
= 2^n
At each step we are dividing the list into two halves. The merging time is
constant but the number of sub problems increses at each level. So the time'
required will be the product of munber of sub problem to merge and constant time required for merging. Now the total time will be merging time for all the levels and we are evetually merging n items at every level so at every
level the merging time is K*n where k is some contant.So total time will
be l * K*n where l denotes the number of levels .By the theory of binay
trees we know that with n items we will get the height as log(n) so we have
l = logn
So the complexity will be K*n*log(n) . So it is of order O(nlogn)