It will be O (n*log(n)). Recurrence relation will be T(n) = T(n/4) + T(3n/4) + O(n)
Lets just say n=4^p so p=log n in base 4 so this will be the number of steps the array will be divided to get trivial constant size array. at every step , processing done will be O(n) because n -- > for first step (n/4) +(3n/4) --> for second step == n/4 for the first partition and 3n/4 for the second partition obtained in the first step ( n/4 * 1/4 + n/4 * 3/4) + ( 3n/4*1/4 + 3n/4*3/4) -->third step ... ... so on for logn steps. Hence O(n *logn ) Omitting constant factor of base 4. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/THiTmtrNhogJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
