how do we write a recurrence formula from a given code

Question

g(A, i, j) {
print("g", i, j);
n := j-i+1;
if (n == 2) {
if (A[i] > A[j]) swap A[i] and A[j];
}
else {
for(k := 0 to n/4-1) swap A[i+n/4+k] with A[i+n/2+k];
// swap 2nd and 3rd quarters
g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
g(A, i+n/2, j); // recurse on 3rd and 4th quarters
g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters

How would be I deduce a recurrence formula from this code. Does $T(n)$ stand for time? I know the answer is $T(n) =3T\frac{n}{2} + O(n)$ , but why is $T\frac{n}{2}$ where did that come from, can someone explain it in detail step by step on how the answer concludes to $T(n) = 3T\frac{n}{2} + O(n)$. Thanks

Answer 1

The function g() calls itself recursively with half the number of array elements to sort three times. That explains the $\,3T(\frac{n}2)\,$ in the equation $\,T(n) =3T(\frac{n}2) + O(n).\,$ If it does not call itself, then it may have to swap two elements which is assumed to take constant time $\,T(2) = 1.\,$ All of these constant time operations are included in the $\,O(n)\,$ which hides a remainder term whose size is less than a constant multiple of $\,n.$