# Mathematically calculating time complexity

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?

• You can learn about substitution method and recursion tree method. Yes all the examples can be estimated. – Navjot Singh Sep 23 '18 at 21:03
• Possible duplicate of Is there a system behind the magic of algorithm analysis? – David Richerby Sep 23 '18 at 22:19
• You're asking for general methods to compute running times; that's exactly what the question I linked does. – David Richerby Oct 23 '18 at 23:24

In the second example, at each iteration i is multiplied either by 2 or by 3. Therefore after k iterations, $$2^k ≤ i ≤ 3^k$$. The number of iterations until i ≥ n is between $$log_2 (n)$$ and $$log_3(n)$$ which is in each case $$O (log(n))$$.
On the other hand, I'm currently working on an algorithm where I don't have the slightest idea how to calculate the runtime, although measurements show that it takes experimentally about $$600 n^{1/2}$$ nanoseconds for values from $$10^{12}$$ to $$10^{19}$$ - with huge variations. A proof for $$O(n^{1/2})$$ is mathematically beyond me.