I need to know the time complexity and space complexity of the following algorit
ID: 3701611 • Letter: I
Question
I need to know the time complexity and space complexity of the following algorithm, in O NOTATION:
function findValues(double[] stack, int elementSize)
{
double[] returnVal = new double[stack.Count]
if ((stack.Count == 0) || (elementSize <= 0)) {
return returnVal
} else {
int step = 0
double valuesSum = 0
for (int i = 0; i < stack.Count; ++i)
{
valuesSum += stack[i]
if (i >= elementSize)
{
valuesSum -= stack[step]
++step
returnVal[i] = (valuesSum / elementSize)
}
else
{
returnVal[i] = (valuesSum / (i + 1))
}
}
}
return returnVal
}
Time complexity, I came up with O(n) for worst-case and O(1) for best-case. Space complexity, I have no idea how to find, I believe it may be O(1) but I'm not sure about the array declaration in the begnning and the sizes of variables changing in the middle. Any help would be appreciated.
Explanation / Answer
//the time complexity that you have calculated is correct that is O(n)
function findValues(double[] stack, int elementSize)
{
double[] returnVal = new double[stack.Count];//space...O(n)//n size of stack
if ((stack.Count == 0) || (elementSize <= 0)) {
return returnVal//constant time
} else {
int step = 0
double valuesSum = 0
for (int i = 0; i < stack.Count; ++i)//O(n) time, n is stack count
{
valuesSum += stack[i];///O(n) time
if (i >= elementSize)
{
valuesSum -= stack[step]
++step
returnVal[i] = (valuesSum / elementSize)
}
else
{
returnVal[i] = (valuesSum / (i + 1))
}
}
}
return returnVal
}
//the overalll complexity of this algorithm is O(n)
//and space complexity is O(n)..because additional array is taken