When the recurrence relation for both are same , why they both getting different result?
Q1. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?
ANSWER: recurrence relation gives,T(N) = T(N/3) + T(2N/3) + N on solving T(N) = N(log3/2N)
Q2. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
ANSWER:recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving we get (n Log n).
My doubt is If for first case it is N(log3/2N) then for second case also it should be N(log4/3N) BUT its not. WHY?