Write the recurrence equation for the running time Tn of the

Write the recurrence equation for the running time T(n) of the ReverseArray function below.

Assume n=r-p+1 is the size of the array A at input.

ReverseArray(A,p,r)

1 if (p<r)

2 n=r-p+1

3 ReverseArray(A,p+1,r-1)

4 tmp=A[p]

5 A[p]=A[r]

6 A[r]=tmp

ReverseArray(A,p,r)
1 if (p<r)
2    n=r-p+1
3    ReverseArray(A,p+1,r-1)
4    tmp=A[p]
5    A[p]=A[r]
6    A[r]=tmp

T(n) = T(n-2) + O(1)
   = T(n-4) + O(1) + O(1)
   = T(n-6) + O(1) + O(1) + O(1)
   = O(1)+O(1)+O(1)+....... n/2 times
   =O(n/2)
   =O(n)

Note: O(1): time taken to swap two numbers