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;
}
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:
To expand the sums, I used the formula for summing consecutive numbers in an arithmetic sequence.