Algorithm Assignment Example | Topics and Well Written Essays - 1750 words

Algorithm - Assignment Example The time taken for reversing the array would be linear to the length of the subsequence at each round. The time taken for palindromic check would also be linear to half of the length of the subsequence returned at each round. Hence, the total time for the algorithm would be O (n2). For the subsequence x [i†¦j] to be palindromic, the element x[i] should be equal to x[j], the element x [i+1] should be equal to x [j-1] and so on. Hence, to compute L (i, j), the elements x [i] and the element x [j] are first checked for equality. If equal, then we can say that L (i, j) holds at least a minimum value of 2 and the equality check is repeated for the next element x [i+1] and x [j-1]. If not equal, it is concluded that at least one of the element is not included in the palindrome. In that case, we are interested in repeating the check for elements x[i] and x [j-1] as well as x [i+1] and x [j] as we are not sure which element is not included in the palindrome. In the worst case, if none of the elements match, then L (i, j) is equal to 1 as every element is a palindrome of itself. Complexity analysis: As the computation involves two for loops, one running n-1 times which is O (n) and the other running n-s times which is also O (n), the total running time for the algorithm would be O (n2). Let be the median of x1, x2, x3.... As median occurs at i= (n+1)/2, we can say that there are (n+1)/2 -1 element smaller the median and there are n-(n+1)/2 elements larger than Sum of the weights of the elements lesser than the median can be written as: From the above analysis in (a), we found that the sum of the weights of all elements smaller than the weighted median is less than  ½. Similarly the weight of all elements larger than the median is also less than 1/2. We can compute xk by recursively calling the deterministic SELECT to compute the regular median. In each round, the array is divided into two halves around the calculated median xm and the actual median xk