Data structure

Question

What is the running time of the function?

Int function(int n) {

If(n<=1)return;

For(int i=1;i<n;i++);

For(int j=0;j<3;j++);

Function (n-1);

Answer 1

int function(int n) {
    if(n<=1)return 1; //means function stops when n=1,i.e.,T(1)=0
    for(int i=1;i<n;i++); //runs (n-1) times, i.e., O(n)
    for(int j=0;j<3;j++); //runs 3 times, i.e., constant or O(1)
    function(n-1); // T(n-1)
}

function() stops when n=1, i.e., T(n-(n+1)) is the last time function() is called.

From the code,

$T(n) = n + T(n-1)$  ---(equation 1)

Therefore,

$T(n-1) = (n-1) + T(n-2)$

$T(n-2) = (n-2) + T(n-3)$

$T(n-3) = (n-3) + T(n-4)$

Using above in equation 1, we get

$T(n) = n + (n-1) + (n-3) + ...... + (n-(n+1))$

$T(n) = n^{2} - (1+2+3+...+(n+1)) $

$T(n) = n^{2} - \frac{(n^{2}+3n+2)}{2}$

$T(n) = \frac{(n^{2}-3n-2)}{2}$

$T(n) = O(n^{2})$