I have the code snippet:
int const n = 300;
int nArr[n];
for(int i = 0; i<n; i++) {
if(i >x)
copyPrevious(nArr,i);
}
I need to find the complexity for the cases when x = 300 and x = 5.
I have already reasoned that the x = 300 case will give O(n) complexity, based on n + 2 assignments, since it never enters the if statement.
However, for 5, I am a little confused. This time, the if statement is relevant, and I don't know how to handle it, since I don't know the particulars of the copyPrevious function. The only thing I know about it is that it itself has complexity O(n).
My usual approach is to make a table of the different parts of the code and the assignments that occur inside and outside the loops. Obviously, the for loop assigns i++ a total of n times, but what of the copyPrevious function? How do I treat it in this manner when I know only a particular x and its complexity?
Any help would be greatly appreciated!
Assume that
copyPrevious(arr,i)has a running time of $O(i)=Ci$ for some constant $C>0$. Basically, you are trying to compute: $$ \begin{align*} \sum_{i=0}^{n-1} 1+\sum_{i=x+1}^{n-1}Ci &= n +C[(x+1)+(x+2)+\cdots+(n-1)] \\ &= n+C \left[\dfrac{n-x-1}{2}(x+n) \right] \\ &= n+C \left[\dfrac{n-5-1}{2}(5+n) \right] \\ &= n+\dfrac{C}{2} (n-6)(n+5) \\ &= n+\dfrac{C}{2} (n^2-n-30) \\ &= \dfrac{C}{2}n^2 + \left(1-\dfrac{C}{2} \right)n -\dfrac{C}{2}30 \\ &= O(n^2)\\ \end{align*}$$