Q:

Time complexity for modification on quicksort

Let a function named QUARTERSORT which gets an array and sort it in the following way:

If n<100` it uses the regular QUICKSORT
Otherwise, we split the array to on A1 = A[1,...,n/4] and A2 = A[(n/4)+1,...,n].
Then, we call QUARTERSORT twice: B1 = QUARTERSORT(A1) and B2 = QUARTERSORT(A2).
Finally, we merge B1 and B2.

Now, why is the recurrence T(n) = T(0.25n) + T(0.75n) + O(n) and not T(n) = T(0.25n) + T(0.75n) + O(nlogn)?

A:

Intuitively, you can ignore the part about quicksort, because it only happens for small n, and the big-O notation only talks about values of n that are "big enough". So the parts of the algorithm are:

Recursive invocation on 1/4 of input: T(1/4 * n)
Recursive invocation on 3/4 of input: T(3/4 * n)
Merging: O(n)

A bit more formally: time complexity of quicksort is O(1). This addition can be safely ignored, because there are larger parts in the time complexity, like O(n).

