Search code examples
algorithmmathcomplexity-theory

What is the T(s) equation for this function?


What is the exact running time for this function?

and I'm a CS student, so I want some resources to help calculate T(s), but really I do need help in this code.

int function(int arr[], int s)
{
    // arr is array of size s
    int m = 0;
    for (int i = 1; i <= s; i++)
    {
        for (int j = i; j <= s; j++)
        {
            int sum= 0;

            for (int k = i; k <= j; k++)
                a+= arr[k];

            m= max(a, m);
        }
    }
    return m;
}

Solution

  • As n is not a variable in this procedure, the T(n) = 1

    Assuming, that you are actually looking for T(s) let's count it together:

    We have the outer-most loop (I), the inner-most loop (III) and the middle loop (II) and T_I(s) is what we are looking for:

    T_III(i,j) = j-i+1
     T_II(i,s) = sum(T_III(i, j) for j in [i, s])
        T_I(s) = sum(T_II(i, s) for i in [1, s])
    

    The T_I(s) can be further expanded into:

    enter image description here

    To expand the sums, I used the formula for summing consecutive numbers in an arithmetic sequence.