This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.
Also I understand that it's impossible to calculate every function, but usually we can (otherwise we have not been asked to do so on the exam).
I know how to mathematically calculate the time complexity of the following function:
for(i = 0; i <= n-1; i++) {
for(j = i + 1; j <= n - 1; j++) {
// loop body - const O(1)
}
}
I would calculate it as following: (hope without mistakes)
$$\begin{align*} \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1 & \overset{(1)}{=}\sum_{i=0}^{n-1}((n-1)-(i+1)+1)\\ &=\sum_{i=0}^{n-1}(n-i-1)\\ &=n\cdot\sum_{i=0}^{n-1}1-\sum_{i=0}^{n-1}i-\sum_{i=0}^{n-1}1\\ &\overset{(2)}{=}n\cdot\sum_{i=0}^{n-1}1-\sum_{i=1}^{n-1}i-\sum_{i=0}^{n-1}1\\ &\overset{(1)}{=}n\cdot((n-1)-0+1))-\sum_{i=1}^{n-1}i-((n-1)-0+1)\\ &=n^{2}-n-\sum_{i=1}^{n-1}i\\ &\overset{(2)}{=}n^{2}-n-\frac{(n-1)\cdot n}{2}\\ &=\frac{2n^{2}-2n-n^{2}+n}{2}\\ &=\frac{n^{2}-n}{2}\\ &=O(n^{2}) \end{align*}$$
when I use the following equations:
$$\sum_{i=m}^{n}1=n-m+1 \,\,\,(1)$$ $$\sum_{i=0}^{n}i=\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \,\,\,(2)$$
But when I get across with much harder function, as following:
example 1:
int x = 2;
while (n < x) {
x *= x;
}
example 2;
int i = 1;
while(i < n) {
if((n – i) % 2)
i *= 3;
else
i *= 2;
}
I get lost. I really don't know where to start calculating. I always can start inserting different values for n
, and guessing the time complexity, but it does not feels right (and also it can be misleading).
Is it even possible to mathematically calculate the time complexity of those examples? how should I approached those questions? Maybe is there somewhere a list of possible tricks?